二分搜索

采用分治的思想,对已经排序的数据每次进行减半的搜索,从而快速减少运行时间。

初始化区间

一般来说,初始化的区间可以分成两种。一种是左闭右闭,也就是 [left, right];还有一种是左闭右开,也就是 [left, right)。区间的选择和后面的边界条件判断以及循环不变体的终止条件需要保持一致。

循环不变体

循环不变体一半是两种,分别是 left<rightleft<=rightleft<right 对应的初始化区间为 [left, right)left<=right 对应的初始化区间为 [left, right]。理解这个对应关系,可以假设只剩下一个元素,或者输入数组只有一个元素时候,显然左闭右闭需要 =,因为还需要进一步判断这个数字是不是目标数字;而左闭右开不需要,因为 left=right 已经取不到数了。

边界条件

如何在循环体里面更新左右两个边界,是需要根据初始化区间。首先 left 都是闭区间,当 target>nums[mid] 的时候,那么 left 肯定要更新为 mid+1,因为 mid 以及之前的都数字都不满足。对于右边,当 right 也是闭区间的时候,分析和前面的左区间类似,肯定也是更新为 mid-1;当 right 为开区间,因为取不到 right 下标对应的数字,而且已经知道 nums[mid]>target,所以更新 right 为 mid 即可。

1
2
3
4
5
6
7
8
9
10
11
template<typename T>
int binary_search(T lst[], int length, T target) {
int head = 0, tail = length - 1;
while (head <= tail) {
int mid = (head + tail) / 2;
if (lst[mid] == target) return mid;
if (lst[mid] > target) tail = mid - 1;
else head = mid + 1;
}
return -1;
}

优化

上面的循环体中,需要比较两次,而且需要满足输入数组中没有重复的数字。可以优化成只要一次比较,并且可以返回重复数字的第一个或者最后一个下标。下面以 Leetcode 上的 34 题为例,说明如何减少比较次数和返回重复数字的下标。

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1].

使用二分搜索分别求左右边界,需要注意循环不变体,以及 mid 的赋值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
vector<int> searchRange(vector<int> &nums, int target) {
int left = 0;
int right = nums.size() - 1;
int mid;
vector<int> result(2, -1);
if (nums.empty()) {
return result;
}
while (left < right) {
mid = left + (right - left) / 2;
if (target > nums[mid]) {
left = mid + 1;
} else {
right = mid;
}
}
if (nums[left] == target) {
result = {left, left};
} else {
return result;
}
right = nums.size() - 1;
while (left < right) {
mid = left + (right - left) / 2 + 1;
if (target < nums[mid]) {
right = mid - 1;
} else {
left = mid;
}
}
result[1] = right;
return result;
}
};

这里的循环不变体是和之前分析的有点不同,因为这里当 left 等于 right 的时候,跳出循环,然后判断是否相等,此时的 left 为不小于 target 数字中的最小值的下标。如果不相等,那么数组中就不存在该数字。然后 left 保持不变,right 归位到最右边。下面的二分搜索有点不同的地方是 mid 的赋值,因为第一个二分搜索中,mid 一直是往左偏的,这里要的到不小于 target 数字中的最小值的最后一个下标,需要 mid 往右偏。

总结

初始化 left 和 right 决定了取值的区间是闭区间还是开区间;循环不遍体需要根据目标结果来判断,主要的依据是 left 和 right 相等的时候还要不要进入循环体;mid 的赋值会影响中间值往左偏还是往右偏;当相等的情况合并到大于或小于的情况,减少比较次数,需要在跳出循环后判断是不是所找的数字的下标。不同条件下要灵活应用二分搜索。