面试中的二分查找

描述二分查找

手写二分查找

考察查找次数

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

算法描述

  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$$

Last modification:January 12, 2022
如果觉得我的文章对你有用,请随意赞赏