二分查找有着查找速度快，平均性能好等优点，但必须要求待查表为有序表，且插入删除困难
看看JDK二分查找源码中的实现

private static int binarySearch0(int[] a, int fromIndex, int toIndex,int key) {        int low = fromIndex;        int high = toIndex - 1;        
        /* 如果改为 low < high，就有可能出现本来数组中有待查元素，却查不到的情况
          比如查10，前两次查找和查12一样，最后low和high指向了元素10，
          但是此时while(low<high)不成立，所以会跳出循环    
         */
        while (low <= high) {            int mid = (low + high) >>> 1;//使用位操作,效率高
            int midVal = a[mid];            if (midVal < key)
                low = mid + 1;            else if (midVal > key)
                high = mid - 1;            else
                return mid; // 找到目标
        }        return -(low + 1);  // 没找到目标.
    }

复杂度分析

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

最坏情况（即查不到）

假设二分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)

折半后，要对一半元素进行遍历，复杂度是O(n),所以算法的时间复杂度为O(n * lg(n))

作者：芥末无疆sss
链接：https://www.jianshu.com/p/e0c8e48cdc4c
來源：简书
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。