稀有猿诉

十年磨一剑,历炼出锋芒,说话千百句,不如码二行。

Binary Search Made Easy

二分查找是效率特别高的一种算法,它能将线性复杂度O(n)降低到对数级别O(logn)。但它对输入数据有要求,比如对于数组来说必须是排序的,否则是不能应用二分的。今天就来理解一下二分查找,然后总结常见的题目和注意事项。

理解二分查找

二分查找的特点是每次能把输入数据分成一半,这样不断的二分下去,直到只剩下一个。所以能应用二分查找的最重要的条件是要能够依据某种条件把输入数据分为两段,最常见的是排序数组查找,但并不限于这个,只要能依据某种条件把数据分成二份,就可以应用二分查找,比如数据是某种情况下的单调性?或者数据有明显的断崖,或者数据是山峰形状的,或者是山谷形状的都可以应用二分查找。二分查找博大精深,需要好好体会其二分的内涵。

对于升序排序数组查找的标准二分代码模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
int left = 0;
int right = n - 1;
while (left <= right) {
    int mid = left + ((right - left) >> 1);
    if (nums[mid] == target) {
        return mid;
    } else if (nums[mid] > target) {
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}
return -1;

注意事项

注意事项就是,区间的开闭,以及中间索引的计算。循环的退出条件一般都是有等号的left <= right时循环。

对于有些情况索引会特别的大,造成计算中间索引时会发生溢出,这时就要先减后加,以防溢出:

1
int mid = left + ((right - left) >> 1);

另外,这里的括号都不可省略,虽然移位符的优先级高于加法,但如果left等于right时,不加括号这个运算会出错。

常见题目

题目 题解 说明
167. 两数之和 II - 输入有序数组 题解 标准二分查找
658. 找到 K 个最接近的元素 题解 找第一个小于等x的位置
977. 有序数组的平方 题解
278. 第一个错误的版本 题解 如何防范溢出
704. 二分查找 题解 标准二分查找
700. 二叉搜索树中的搜索 题解 BST中的二分查找
题解
题解

参考资料

Comments