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

理解二分查找

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

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

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时，不加括号这个运算会出错。

常见题目

参考资料