二分搜索

二分搜索,采用分治的思想,对已经排序的数据每次进行减半的搜索,从而快速减少运行时间。短时间内写出 bug free 的二分搜索还是有点小困难。

《编程珠玑》的作者 Jon Bentley 曾在贝尔实验室做过一个实验,即给一些专业的程序员几个小时的时间,用任何一种语言编写二分查找程序(写出高级伪代码也可以),结果参与编写的一百多人中:90% 的程序员写的程序中有 bug(我并不认为没有 bug 的代码就正确)。

也就是说:在足够的时间内,只有大约 10% 的专业程序员可以把这个小程序写对。但写不对这个小程序的还不止这些人:而且高德纳在《计算机程序设计的艺术 第 3 卷 排序和查找》第 6.2.1 节的“历史与参考文献”部分指出,虽然早在 1946 年就有人将二分查找的方法公诸于世,但直到 1962 年才有人写出没有 bug 的二分查找程序。

要点

初始化区间

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

循环不变体

循环不变体一半是两种,分别是 left < rightleft <= rightleft < right 对应的初始化区间为 [left, right) , left <= right 对应的初始化区间为 [left, right] 。理解这个对应关系,可以假设只剩下一个元素,或者输入数组只有一个元素时候,显然左闭右闭需要 = ,而左闭右开不需要,否则就不能找出目标数字。

边界条件

因为左边界都是闭区间,所以 left = mid + 1 。但是对于右边界分成两种情况,如果是闭区间,那么 right = mid - 1,如果是开区间,那么 right = mid 。假设是闭区间,但是又写成 right = mid ,同时根据上面的分析,循环不变体是 left <= right ,那么就会进入死循环,举个例子,输入数组为 [11] ,目标为 12 。那么 left 等于 0 ,right 等于 0 ,mid 等于 0 。这时候 right = mid = 0 ,会一直循环。假设是开区间,但是又写成 right = mid - 1 ,同时根据上面的分析,循环不变体是 left < right ,那么可能会错过目标数字,假设输入为 [11, 12, 13, 14] ,目标数字为 12 。么 left 等于 0 ,right 等于 4 ,mid 等于 2 。此时 nums[2] = 13 > 12right = mid - 1 = 1 ,那么区间就变成 [0, 1) 。已经不能找到目标数字 12 。

例子

Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the 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
class Solution {
public:
int search(std::vector<int> &nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target <= nums[mid]) {
right = mid;
} else {
left = mid + 1;
}
} else {
if (nums[mid] <= target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
}
return -1;
}
};

如果 nums[left] <= nums[mid] ,那么 [left,mid] 一定为单调递增序列。

Search in Rotated Sorted Array II

Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Write a function to determine if a given target is in the array.
The array may contain duplicates.

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
class Solution {
public:
bool search(vector<int> &nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[left] < nums[mid]) {
if (nums[left] <= target && target <= nums[mid]) {
right = mid;
} else {
left = mid + 1;
}
} else if (nums[left] > nums[mid]) {
if (nums[mid] <= target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid;
}
} else {
++left;
}
}
return false;
}
};

既然 nums[left] <= nums[mid] 不能确定递增,那就把它拆分成两个条件:

  • 若 nums[left] < nums[mid],则区间 [left, mid] 一定递增
  • 若 nums[left] == nums[mid],不能确定是否递增,那就 ++left,缩小一步区间范围

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

1
2
3
4
5
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]

Given target = 3, return true.

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:
bool searchMatrix(vector<vector<int>> &matrix, int target) {
if (matrix.empty()) {
return false;
}
int m = matrix.size();
int n = matrix[0].size();
int left = 0;
int right = m * n;
while (left < right) {
int mid = left + (right - left) / 2;
if (target == matrix[mid / n][mid % n]) {
return true;
}
if (target < matrix[mid / n][mid % n]) {
right = mid;
} else {
left = mid + 1;
}
}
return false;

}
};

Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

For example,
Consider the following matrix:

1
2
3
4
5
6
7
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

Given target = 5, return true.
Given target = 20, return false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
bool searchMatrix(vector<vector<int>> &matrix, int target) {
if (matrix.empty() || matrix[0].empty()) {
return false;
}
int m = matrix.size();
int n = matrix[0].size();
int i = 0;
int j = n - 1;
while (i < m && j > -1) {
int num = matrix[i][j];
if (target == num) {
return true;
} else if (target > num) {
++i;
} else {
--j;
}
}
return false;
}
};