二分搜索的时间复杂度分析

先贴上二分查找的java代码实现

public static int binarySearch(int[] a,int n,int value){
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = (low + high) >> 1;
            if (a[mid] == value) {
                return mid;
            } else if (a[mid] < value) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

时间复杂度，其实就是分析代码执行的次数。
in low = 0和int high = n - 1就不说了，都是常量级的执行时间，对总的执行时间影响不大。
关键是while循环中的代码执行次数是多少次？
while循环的代码，很简单，就是每次取中间的数和目标值进行比较。我们来分析一下执行的过程
第一次：n/2
第二次：n/2²
第三次：n/2³
。
。
。
。
第k次：n/2的k次方
可以看到每比较一次，数据量就减少一半。最坏的情况下，直到待查找数组只剩最后一个元素时，才匹配到目标值。此时待比较的数据量就只剩1个。
输入法不好打出对数和k次方，所以此处借用极客时间的一张图。来说明一下

所以二分搜索的时间复杂度是O(logn)