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

理解二分查找

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

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

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
2
3
4
5

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

// or

int mid = left + (right - left) / 2;

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

非标准二分

有很多时候是用不上标准二分的，比如像寻找比某个数大的数（位置），寻找比某个数小的数（位置），数据仍然是有序的，依旧可以应用二分查找。

升序（非降序）中寻找第一个比目标大（不小于）的数

二分性的要点，第一个比目标大（不小于目标），那么假设arr[i]比目标大，那么arr[i-1]一定比目标小，所以当arr[mid]大于等于目标时向左找，否则向右找。伪码如下：

1
2
3
4
5
6
7
8
9
10
11
12

    left = 0
    right = len(arr)
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] >= target:
            if mid == 0 or arr[mid - 1] < target:
                return mid
            right = mid - 1
        else:
            if arr[mid + 1] >= target:
                return mid + 1
            left = mid + 1

降序中寻找最后一个不小于目标的数

区间二分

要寻找的目标并不是一个数值，而是一个区间，也是可以应用二分查找 的。

断崖和山峰或者山谷

断崖也就是说数组分成两段，每段都是递增的；山峰也就是中间是最大向两边递减；山谷是中间最小向两边递增。这些数据都具有明显的二分性，都可以应用二分查找。整体思路不难，但要处理魔鬼细节。

典型题目

二分库函数

二分查找是一个比较流行的算法，使用的也较多，因此绝大多数语言的标准库中都有此算法。

C语言：

1
2
3

#include <stdlib.h>

void *bsearch(const void *key, const void *base, size_t nitems, size_t size, int (*com)(const void *, const void *))

C++：

1

std::binary_search(start, end, target)

Java：

1
2
3
4

import java.util.Arrays;

int i = Arrays.binarySearch(arr, target);
// 返回是target所在的索引，或者其可以插入的索引的负值

Python3：

1
2
3
4

from bisect import bisect_left, bisect_right

left_most = bisect_left(arr, target)
right_most = bisect_right(arr, target)

Kotlin：

1
2
3

// binarySearch is an extension funtion of List
arr = listOf(1, 2, 3, 4, 5)
val i = arr.binarySearch(target)

完全二分

在大多数的二分查找中，我们说时间复杂度是O(logⁿ)，在算法分析中大O的意思是平均时间复杂度，但是很多二分查找是会提前退出的，因为会检查mid所在的元素是否满足，如果满足就终止查找过程了，所以很多时候真实运行的复杂度是小于logⁿ的。

但有些时候，是没有条件帮你判断可以提前退出的，必须不断的压缩区间范围直到只剩下最后一个元素，运行的时间复杂度一定达到logⁿ，这便是完全二分。

比如说寻找升序中比target大的第一个数，就可以用完全二分，来不断的压缩范围，直到最后一个就是答案：

1
2
3
4
5
6
7
8
9
10

  # Find first item bigger than target
    left = 0
    right = n - 1
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return arr[left] # or arr[right]

可以看出，完全二分的特点，循环不变式的条件要是开的（没有等于条件），符合查询条件的一半时，直接把边界设置为mid，而不是跳过（也即不加1或者减1），最后左右边界一定相等，并且就是答案。

高难度二分

高难度二分的难点在于如何找到数据的二分性，也就是如何看待数据，以及如何找条条件以让其能具有二分性，这是应用二分的前提，具体情况比较繁多，视具体的数据类型与范围而定，没有明确的范式可以归纳，只能稍作总结。

区间开闭和边界检查

二分查找思路并不难，但它有魔鬼细节，比如说区间是用开的，还是闭的，比如循环不变式到底要不要用等于，再比如要不要检查 数组的边界，我们来稍作总结一下：

输入区间只能半开半闭，最好全是闭区间

二分查找必须界定一个查找区间，这个区间必须有一端是闭的，至于另外一端可开可闭，但最好全是闭区间。

如果是半开半闭，那么循环不变式终止条件一定不能有等于号。

循环不变式的终止条件

如果没有等于号，那么循环不变式终止时，左右界相等，指向同一个元素，循环不变式最后一次循环体内，左历界指向一对相邻的元素；

同理，如果有等于号，终止时左界超过右界，最后一次循环时左右界相等指向同一元素。

所以，这里就没有固定范式了，取决 于你在循环体内进行什么样的判断，如果你多判断了前后的元素，那么开式（不带等号）也是对的。

一般的建议：区间闭，循环体内有return时用闭式（带等号的），完全二分压缩区间时用开的，当然 你用闭的也可以，只不过最后把left-1当成答案。

参考资料

• Binary Search – Data Structure and Algorithm Tutorials
• Data Structure and Algorithms Binary Search
• 二分查找从入门到入睡