面试中的二分查找

描述二分查找

手写二分查找

考察查找次数

二分查找用于快速索引一个元素的位置，假设有一个已经排好序的数组，我们取中间位置跟目标元素比较，目标元素大，往右继续找中间，目标元素小，往左继续找中间。

算法描述

1. 前提：已有排序数组 A（假设已经做好）
2. 定义左边界 L、右边界 R，确定搜索范围，循环执行二分查找（3、4两步）
3. 获取中间索引 M = Floor((L+R) /2)

4. 中间索引的值 A[M] 与待搜索的值 T 进行比较

   1. A[M] == T 表示找到，返回中间索引
   2. A[M] > T，中间值右侧的其它元素都大于 T，无需比较，中间索引左边去找，M - 1 设置为右边界，重新查找
   3. A[M] < T，中间值左侧的其它元素都小于 T，无需比较，中间索引右边去找， M + 1 设置为左边界，重新查找
5. 当 L > R 时，表示没有找到，应结束循环

public class BinarySearch {
    public static void main(String[] args) {
        int[] ints = {1, 5, 8, 9, 12, 15, 16, 19, 22, 44, 52, 66, 158};
        int i = binarySearch(ints, 66);
        System.out.println(i);
    }

    public static int binarySearch(int[] ints, int t) {
        //左
        int l = 0;
        //右
        int r = ints.length - 1;
        //中间
        int m;
        while (l <= r) {
            //m = (l + r) / 2; 可能内存溢出
            m = (r - l) / 2 + l;
            if (t > ints[m]) {
                l = m + 1;
            } else if (t < ints[m]) {
                r = m - 1;
            } else {
                return m;
            }
        }
        return -1;
    }
}

问题：

1. 有一个有序表为 1,5,8,11,19,22,31,35,40,45,48,49,50 当二分查找值为 48 的结点时，查找成功需要比较的次数
2. 使用二分法在序列 1,4,6,7,15,33,39,50,64,78,75,81,89,96 中查找元素 81 时，需要经过（ ）次比较
3. 在拥有128个元素的数组中二分查找一个数，需要比较的次数最多不超过多少次

算剩下元素个数/2，结果是奇数则+1，找到这个位置进行比较，偶数不变。

1. 13个元素，13/2 = 6(舍去小数) 找第7个，31 < 48，往右算剩下6个元素，6/2 = 3 继续找第3个，45 < 48，剩下3个，找第2个，49 > 48 找左边，剩下一个（根据上面的算法代码这里要比最后一次！！！）一共4次，另外二分查找还有别的算法，可能只需要比3个，道理也很简单。
2. 14个元素，第7个，39 < 81，剩下7个，找第4个，75 < 81，剩下3个，找第2个，89 > 81，左边一个比最后一次。一共4次。
3. 2^n = 128，算 n 即可。计算器中只能算10为底的对数，可以用换底公式，$$n = log_2N = log_{10}N/log_{10}2$$