二分查找 - Locam's Castle

关于二分查找

二分查找的实现思想可谓是十分简单，它的查找过程如下：

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。–摘自百度百科

代码实现

我们先给出比较容易理解的伪代码以及Java和python3和JavaScript实现：

int binarySearch(ary, target){
    left = 0, right = ary.length - 1; // 初始左边界为下标0，右边界为下标数组.长度 - 1(即数组最后一个元素)
    while(left <= right){             // 当左边界和右边界交叉时退出循环
        mid = (left + right) / 2;     // 中间位置
        if(ary[mid] < target){        // 当中间值小于目标值时，所以下一步要到(mid, right]中去找
            left = mid + 1;           // 因此把left更新为mid + 1
        }
        else if(ary[mid] > target){
            right = mid - 1;          // 同理，若中间值大于目标值，则将right更新为mid - 1
        }
        else {
            return mid;               // 当mid处的值既不大于也不小于target的时候，则找到目标值，返回下标mid
        }
    }
    return -1;                        // 循环执行完毕还没找到，则返回-1表示没找到目标值
}

public int binarySearch(int[] ary, int target){
    int l = 0, r = ary.length - 1;
    while(l <= r){
        int mid = l + (r - l) / 2;    //这么写可以防止l+r对于int类型溢出
        if(ary[mid] < target){        
            left = mid + 1;           
        }
        else if(ary[mid] > target){
            right = mid - 1;          
        }
        else {
            return mid;
        }          
    }
    return -1;
}

def bin_Search(ary: List[], target: int) -> int:
    l, r = 0, len(ary)
    while l <= r:
        mid = (l + r) // 2          # python3的int理论上讲可以无限大，不需要担心溢出
        if ary[mid] < target:
            l = mid + 1
        elif ary[mid] > target:
            r = mid - 1
        else:
            return mid
    return -1

/**
 * @param {number[]} ary
 * @return {number}
 */
const binarySearch = () => {
    let l = 0, r = ary.length;
    while(l <= r){
        let mid = l + Math.floor((r - l) / 2);
        if(ary[mid] < target){        
            left = mid + 1;           
        }
        else if(ary[mid] > target){
            right = mid - 1;          
        }
        else {
            return mid;
        }          
    }
    return -1;
};

因为二分查找每次查找都会使查找长度减半，第一次为n，第二次为n/2，第三次为n/2^2，…n/2^k，…，其中k为循环次数，令n/^k=1，则k=log2n，所以二分查找时间复杂度为O(logn)。
由于使用了常数级辅助空间(l，r和mid)，所以空间复杂度为O(1)。

细节问题

关于循环不变量：上面while循环中的条件是*l<=r*，也就是说我们的查找区间是一个闭区间[l,r]，在整个循环过程中都是如此(循环不变)，所以l和r都可以取到，因此l=r时是有意义的；当mid处的值小于target时，由于ary[mid]是有意义的，所以下次循环我们比较的区间变为[mid + 1, r]而不是[mid, r];当ary[mid]>target时同理。

结语

到这里是不是对于二分查找有了更清晰的理解了呢，可以自己在本地或者推荐到菜鸟教程的在线测试环境中用几个例子测试一下。
一般来说，绝大多数情况下使用二分查找需要数组有序，特殊情况可以将数组用其他方法指标分类时可以无序。
二分查找的区间还可以写为(l,r]，这种写法的循环条件以及判断条件和更新语句怎么写就可参照上面的分析方法去做，具体此处不再赘述。
后续会更新具体的一道二分查找变体的题目，敬请期待。