思想
二分查找也是有一套模板的，可以用如下的步骤总结：
- 使用前提：元素在某种程度上有序；
- 明确下标的含义与边界；
left, right 赋值与计算中间 mid；- 当决策边界合法时，进行判断；
- 根据条件剪枝，并得到新的边界；
- 边界非法，跳出循环，得到结果。
这 6 步具体怎么实施，从下面的几道题来讨论。
题目
先从一道 Hard 开始，它要求我们找到两个有序数组中的中位数。
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
37
38
39
| class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
if (m > n) {
return findMedianSortedArrays(nums2, nums1);
}
int left = 0, right = m;
while (left <= right) {
int i = left + (right - left) / 2;
int j = (m + n + 1) / 2 - i;
int Aleft = (i == 0 ? INT_MIN : nums1[i - 1]);
int Aright = (i == m ? INT_MAX : nums1[i]);
int Bleft = (j == 0 ? INT_MIN : nums2[j - 1]);
int Bright = (j == n ? INT_MAX : nums2[j]);
if (Aleft <= Bright && Bleft <= Aright) {
if ((m + n) % 2) {
return max(Aleft, Bleft);
}
else {
return (max(Aleft, Bleft) + min(Aright, Bright)) / 2.0;
}
}
else if (Aleft > Bright) {
right = i - 1;
}
else {
left = i + 1;
}
}
return 0;
}
};
|
按照前面的分析，我们走一遍这 6 步。
- 有序吗？有序。两个数组都是有序的，在某种程度上，可以根据有序的性质来剪枝；
- 下标的含义是？下标的含义是，在 idx(从 0 开始) 前开始切割；
- 赋值左右，中间有两个，数组 1 的中间和数组 2 的中间；
- 当左边 <= 右边时，进行循环；
- 什么时候满足条件？当 (数组 1 左 <= 数组 2 右) 且 (数组 2 左 <= 数组 1 右)。剪枝的选择是，如果数组 1 左 > 数组 2 右，说明右边范围太大，反之同理；
- 最后肯定会找到结果。
这道题的难点是，要考虑两个中点。一个中点是传统意义上的，另外一个中点是由中位数的性质引出来的被动中点。由于两个中点的出现，要在最前方加一个条件判断，确保数组 1 的长度比数组 2 的小。
为什么呢？因为根据两个中点的计算方式，数组 2 的中点可能需要做出一些额外贡献，必须保证 i + j 是数组总数的一半(+ 1 )。极端的例子是，数组 2 为空，此时数组 2 最大的合法中点是 0，不可能根据 (m + n + 1) / 2 - i 补足一半。
至于说为什么循环的判断是 left <= right，我认为这和剪枝的方式有关系。如果每次剪枝都是严格的范围减小，那么可以保留等号；否则，有可能出现跳不出循环的情况。
这题就是严格的范围变化，每当中点不满足时，left 或者 right 考虑中点的下一个位置。为什么不赋值 left = mid 或者 right = mid？因为这次判断已经说明了 mid 是非法选择，因此可以考虑下一个。之后我们会看到一个题目，while 内是严格的不等号。
33. Search in Rotated Sorted Array
这题要求我们在经过了循环位移后的数组中找是否存在某个元素。
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
| class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < nums[right]) {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
else {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
}
return -1;
}
};
|
这题是比较经典的模板了，但是稍微有些变形，体现在剪枝并不是无脑地划分一半，而是需要经过一些小巧思的条件判断。
注意到，当数组的左半边递增时，如果目标在左半边，则右半边剪枝；否则左半边剪枝。对于右半边递增的情况，同理。
这里要注意， target 和 nums[left] 或 nums[right] 比较时，需要挂上等号。虽然我觉得，如果真的相等，可以提前终止，但，为了保证二分查找的规范性，还是这样吧。而与 nums[mid] 对应的一端不必挂等，因为上面判断过二者肯定不等。
34. Find First and Last Position of Element in Sorted Array
这题要求我们在有序数组中，找到目标元素的开始下标和结束下标。
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
37
38
39
40
41
42
43
44
45
46
47
| class Solution {
private:
int searchLeft(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1;
int ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid - 1;
if (nums[mid] == target) ans = mid;
}
else {
left = mid + 1;
}
}
return ans;
}
int searchRight(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1;
int ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
if (nums[mid] == target) ans = mid;
}
else {
right = mid - 1;
}
}
return ans;
}
public:
vector<int> searchRange(vector<int>& nums, int target) {
return {searchLeft(nums, target), searchRight(nums, target)};
}
};
|
这题的方法是两次二分，我第一次做，还是考虑的可能不剪枝，同时考虑两边，一下把所有的解都找到，但其实不是最好的。关于二分查找，我认为还是要想办法剪枝，尽量剪枝，符合规范。
至于说这题有什么不同的地方吗？可能需要记录一下 ans，以及反应过来是两次二分。没别的了。
35. Seach Insert Position
这题要求我们找到一个元素在有序数组中的下标，如果没有，则返回插入后在什么位置。
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
| class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] > target) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return left;
}
};
|
很基础的二分查找。值得一提的是关于元素插入时，下标的计算。最后返回的是 left。我觉得可以进行一个简单的推理：
最终，肯定 left == right == mid，分成两种可能。如果 mid 对应的值比 target 小，那么 left + 1，说明元素应该插在当前元素后；反过来，right - 1，但是 left 不变，表示元素插入在当前元素前，并且插入后下标就是当前元素的下标。
74. Search a 2D matrix
这题给了我们一个二维数组，有趣的是，这个二维数组的每一行如果首尾相接，是单调递增的。
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:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int left = 0, right = m * n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int row = mid / n;
int col = mid % n;
if (matrix[row][col] == target) {
return true;
}
else if (matrix[row][col] > target) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return false;
}
};
|
这题是个很基础的二分，和一维的相比，唯一要考虑的是思维的转变：如果把二维数组展平成一维的，那就是很简单的查找了。
124. Binary Tree Maximum Path Sum
这题要求我们找到二叉树中，最大的路径和。这题并不是二分查找，因为不存在有序这个特征。应该放到二叉树专题下，这里不讨论。
153. Find Minimum in Rotated Sorted Array
这题要求我们在一个循环位移后的数组中，找到最小值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
int left = 0, right = n - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[right]) {
right = mid;
}
else {
left = mid + 1;
}
}
return nums[left];
}
};
|
这里，终止条件是严格小于，为什么不能挂等呢？因为当 nums[mid] < nums[right] 时，说明右半边递增，此时 mid 仍然有可能是最小值，所以 right = mid，而不是 mid - 1。此时边界并不是严格减小。
试想，最终必然出现 left == right 的情况，此时已经找到最小值了。如果再挂等，left += 1，反而不是所求。
总之，我还是没太熟稔关于边界是否挂等的判断。但目前的认识是，如果每次范围严格缩小，则需要挂等，因为新的范围严格更小，之前没有探索过，必须再次判断；而如果有至少一边的范围不是严格缩小，则不用挂等，结束条件是收敛到一点，这一点就是答案。
