0. 引子
二分查找是一种高效的搜索算法，常用于有序结构的搜索。
二分查找也是分治法(Divide and Conquer)的一个经典实例：在一个长度为$n$的数组中进行二分查找，其复杂度是$O(logn)$，这是因为二分查找每一次都筛选掉一半搜索区间长度的元素，其递推公式为:
$$
T(n)=\frac{1}{2}T(\frac{n}{2})+O(1)
$$
可根据主定理(Master Theorem)求解。
1. 经典的二分查找
简单的测试程序如下：
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
| #include <vector>
#include <iostream>
using namespace std;
int main(int argc, char **argv) {
vector<int> my_vector;
for(int i = 0; i < 20; ++i) {
my_vector.push_back(i);
}
int left = 0, right = my_vector.size() - 1, target = 19;
while(left <= right) {
int mid = left + (right - left) / 2;
if(my_vector[mid] < target) {
left = mid + 1;
} else if(my_vector[mid] > target) {
right = mid - 1;
} else {
cout << "Find Target At" << mid << endl;
break;
}
cout << "Left: " << left << " Right: " << right << endl;
}
cout << "Left: " << left << " Right: " << right << endl;
return 0;
}
|
while循环里的条件一般是left <= right而非left < right。为什么常用前者？让我们看看输出：
按照程序里的模式，如果将等号省略，输出为：
Left: 10 Right: 19
Left: 15 Right: 19
Left: 18 Right: 19
Left: 19 Right: 19
Left: 19 Right: 19
不省略等号，输出为：
Left: 10 Right: 19
Left: 15 Right: 19
Left: 18 Right: 19
Left: 19 Right: 19
Find Target At 19
Left: 19 Right: 19
搜索21时，省略等号的输出为：
Left: 10 Right: 19
Left: 15 Right: 19
Left: 18 Right: 19
Left: 19 Right: 19
Left: 19 Right: 19
不省略等号的输出为：
Left: 10 Right: 19
Left: 15 Right: 19
Left: 18 Right: 19
Left: 19 Right: 19
Left: 20 Right: 19
Left: 20 Right: 19
当元素存在时：
省略等号，则当left和right相等时，直接退出循环，break存在与否都无所谓，程序不会陷入死循环。
不省略等号，则当left和right相等时，输出提示信息，这时如果不加break，程序将死循环。
这对应着两种需求。前者适用于只要元素下标的情况，比如一维数组的搜索，后者不仅适用于前者的情况，也适用于需要在获取下标的基础上，另外进行一些操作的情况，比如在二维数组中搜索某元素，先搜索列，再搜索行。所以常常使用left <= right的格式。
当元素不存在时：
二者的差别仅在于最后left和right的值。省略等号，二者相等，不省略等号，left大于right，且left和right的差为1。
二分查找的灵活性很强，比如Leetcode 74. Search a 2D Matrix，代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int col = matrix[0].size();
int left = 0, right = matrix.size() * col - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
int ele = matrix[mid / col][mid % col];
if(ele < target) {
left = mid + 1;
} else if(ele == target) {
return true;
} else {
right = mid - 1;
}
}
return false;
}
};
|
2. 寻找左右边界的二分查找
在递增数组中寻找左边界的代码如下：
1
2
3
4
5
6
7
8
9
| while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
int border1 = left;
|
所谓左边界，就是某元素第一次出现的位置，若中间值大于等于目标值，就让右指针左移，略去的值大多都不是元素第一次出现的位置。如果略去了元素第一次出现的位置怎么办呢？可以通过左指针来弥补，因为右指针最远也只能挪移到，元素第一次出现的位置的左侧一格，而最终左指针必然等于右指针指向的值加1，这时左指针必然指向元素第一次出现的位置。
那么寻找右边界的代码也好写啦：
1
2
3
4
5
6
7
8
9
| while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
int border2 = right;
|
这样我们也就快解出了Leetcode 2089. Find Target Indices After Sorting Array。
该题的C++代码如下：
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
| class Solution {
public:
vector<int> targetIndices(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int left = 0, right = nums.size() - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
int border1 = left;
left = 0;
right = nums.size() - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
vector<int> result;
for(int i = border1; i < left; ++i) {
result.push_back(i);
}
return result;
}
};
|
类似的，也有Leetcode 2529. Maximum Count of Positive Integer and Negative Integer，该题只需要将问题转换为求0的左右区间即可，代码如下:
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
| class Solution {
public:
int maximumCount(vector<int>& nums) {
int left = 0, right = nums.size() - 1, target = 0;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
int borderLeft = left;
left = 0;
right = nums.size() - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return max(borderLeft, (int)nums.size() - left);
}
};
|
