真题

对于数列4、5、6、7、9、12、18、23，如果采用折半查找元素9，请问需要查找几次？（）

A、2

B、3

C、4

D、5

解析

折半查找（Binary Search），也称二分查找，是一种在有序数组中查找特定元素的搜索算法。

折半查找的基本思想是将有序数组分成两个部分，比较中间元素与目标值的大小，如果中间元素等于目标值，则查找成功；如果中间元素大于目标值，则在左半部分继续查找；如果中间元素小于目标值，则在右半部分继续查找。这样递归进行直到找到目标值或者查找范围为空为止。

折半查找有几个值得注意的点：

需要查找的数组必须是有序的，且数组中不能存在重复的数字如何找到数组的中间位置？一般是利用（第一元素的角标 + 最后一个元素的角标）/2如果数组是奇数位怎么办？这种好办，找中间位时会直接找到一个中间元素，进行对比即可如果数组是偶数位怎么办？这种找中间位找到的角标一般有小数位，不能直接使用。这个时候一般利用取整来找最近的元素进行比较，比如题目中一共有8个数字，取中间角标为（0+7）/2=3.5，这个时候我们直接取角标为3的元素与需要被查找的元素进行对比，即取7与9进行对比。

利用以上知识，我们推演一下题目中的对比过程：

第一次：我们取中间角标（0+7）/2=3.5，取角标为3的元素，num[3] = 7,而7<9，则舍弃左半部分，利用右半部分再次查找。此时，右半部分为：9、12、18、23。

第二次：我们取中间角标（4+7）/2 = 5.5, 取角标为5的元素，num[5] = 12, 而12>9，则舍弃右半部分，利用左半部分再次查找。此时，左半部分为：9、12。

第三次：我们取中间角标（4+5）/2 = 4.5，取角标为4的元素，num[4] = 9, 而9=9，即找到了此元素。

因此此题的答案为B。

下面是一段java编写的二分查找的示例代码，也可以进行验证：

public class BinarySearchTest {    public static void main(String[] args) {        int[] nums = new int[]{4,5,6,7,9,12,18,23};        binarySearch(nums,9);    }    public static void binarySearch(int[] nums,int num){        //定义结果变量        int i = -1;        int count = 0;        //定义头、尾位置        int head = 0;        int tail = nums.length - 1;        //循环查找        while (true) {            count++;            //定义中间位置            int total = (head + tail);            int middleIndex = total/2;            int middleValue = nums[middleIndex];            //判断是奇数数组还是偶数数组 true为偶数数组            boolean flag = total%2==0?true:false;            //判断结果            if (num == middleValue) {                i = middleIndex;                break;            } else if (num < middleValue) {                //重新定义查找区间                head = head;                tail = flag?(middleIndex - 1) : middleIndex;            } else {                head = middleIndex + 1;                tail = tail;            }            if (head == tail) {                //元素不在数组内，直接返回                break;            }        }        System.out.println("找了" + count + "次！");        System.out.println(i == -1?"未找到该元素":"元素" + num + "在第" + (i+1) +"位上!");    }}