二分查找剖析

mmexport1520334289708.gif

阅读原文

二分查找有着查找速度快，平均性能好等优点，但必须要求待查表为有序表，且插入删除困难。

二分查找思想

在算法国内的另一位大师克，听说了Bill大师给他弟子讲的冒泡排序之后，为了不落于人，决定传授弟子们一种新的算法。

次日，克唤来两名得意弟子谦子和慧子，准备考考他们

谦子和慧子来到老师跟前，只见老师在纸上写了一行数，如下：

1.png
2.png

谦子抢先答道

3.png
谦子急忙问道
4.png
慧子一边说着一边画了个图
5.png

这时慧子又画了一个图

6.png
谦子听了之后不得不佩服
7.png
慧子画出了第三张图
8.png

二分代码

9.png

慧子的代码功底还是非常强的，说着说着写了短短几行代码

private static int binarySearch(int arr[], int key) {
    int low = 0;                          // key 为待查找元素
    int high = arr.length-1;
    int mid;
    while(low <= high) {
        mid = (low + high)/2;    // 查找区间的中间位置
        if (arr[mid] > key) {
            high = mid - 1;
        } else if (arr[mid] < key) {
            low = mid + 1;
        } else {
            return mid;    // 查到返回该元素下标
        }
    }
    return -1;   // 未查到返回-1
}

10.png

慧子解释道

11.png

慧子画出了下图解释道

12.png
这时克发话了

慧子还在欣赏自认为完美无瑕的代码，听了老师的话一下变得紧张起来

13.png
慧子嘿嘿地笑了一下
14.png
15.png
克自问自答起来，顺手画了一个图
16.png
慧子恍然大悟，原来写成 mid=low+(high-low)/2 就可以了

时间复杂度

17.png
你这样想一下，你要查找的数据规模如果是n,那二分一次后规模就变为n/2^{1,二分两次后规模为n/2}2,...,二分m次后规模为n/2^m,若二分m次后跳出循环，则m就是循环的次数（不管查找是否成功）
18.png

下来分析最坏情况，也就是查找不到
前提：查找不到元素

假设你二分m次后剩下一个元素，那么此时规模为1,同时二分m次后规模变为n/2^{m，则：n/2}m = 1, 解出 m = lg(n)，此时再循环一次，查找不到，跳出循环，所以说最多有 m+1 次循环（二分m次未跳出循环，还要二分一次），也就是查找一个元素最多需要m+1次，即lg(n)+1次比较，故二分的最坏时间复杂度为O(n) = lg(n)

lg(n) 这里是以2为底

19.png

说完克看弟子还是不是很明白，说道

20.png

x向下取整表示小于或等于x的最大整数

21.png

完。
招录自：码分享