LeetCode - 二分查找

“90%的程序员不能写出正确的二分查找” – 不是我说的

二分查找及其变种有很多种形式,例如查找第一个出现的、查找出现的区间,等。但都不能脱离一个宗旨:每次查找都要有下标的更迭。

一个经典的二分查找的错误是,出现了下标分别处在了i和i+1,而却判断nums[l] < nums[mid] ? l = mid : r = mid。(这里是不规范的写法)。这会可能导致产生一个死循环,因为,(i + i + 1) // 2 = i。如果第一个判断条件被命中,则永远循环在了那儿。

另外一个不恰当的做法是,判断两边的值,进而判断是否到了边界,然后判断mid值。这种做法可能导致的错误是,l == i, r == i + 1 时,我的mid又要被判断了一次。这种做法是比较冗余的,而且可能导致insidious bug。

基本正确做法是,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool bin_search(vector<int>& nums, int target) 
/* 判断是否存在,且数值不重复的情况 */
{
int l = 0, r = nums.size() -1;
while (l < r) {
int mid = (l + r) / 2;
if (nums[mid] < target)
/* target在 mid左边 */
{
l = mid + 1;
}
else
/* 因为 (i + i + 1) // 2 -> i, r = mid就行了 */
{
r = mid;
}
}
return nums[l] == target;
}

一些变种:

数值存在,找边界:

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
/* LeetCode p34 */

class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.size() == 0) return vector<int>{-1, -1};
int l = 0, r = nums.size() - 1, mid;

int i = l, j = r;

/* 找小边界 */
while (j > l) {
mid = (j + l) / 2;
if (nums[mid] < target) {
l = mid + 1;
} else {
j = mid;
}
}

/* 不存在,返回 */
if (nums[j] != target) {
return vector<int>{-1, -1};
}

/* 找大边界 */
while (i < r) {
mid = (i + r) / 2;
if (nums[mid] <= target) {
i = mid + 1;
} else {
r = mid;
}
}

return nums[r] == target ? vector<int>{l, r} : vector<int>{l, r - 1};
}
};

二分查找的边界条件十分值得注意。很容易出现查找缺漏、死循环的情况。

如有错误,恳请指正!

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×