0%

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
int search(vector<int>& vec, int target) {
int l = 0, r = vec.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (vec[mid] == target)
return mid;
else if (vec[mid] > target)
r = mid - 1;
else
l = mid + 1;
}
return -1;
}

这段代码就是典型的 二分查找 的C++实现。相信每一个程序员都可以自信的写出来。但是实际算法中,往往需要你寻找上界,下界,有时 vec[mid] == target 要和 > 或者 <合并处理。如果你不能自信完美的实现 lower_boundupper_bound,这边文章可以帮助你更好的理解 二分查找的上界,下界等细节的处理。

选择

我们需要在 while (l < r) while (l <= r) while (l < r - 1)

l = mid + 1 l = mid r = mid - 1 r = mid

vec[mid] >= target vec[mid] <= target

之间进行选择

边界

为了避免死循环,以下四种处理都是合法

  1. while (l <= r); l = mid + 1; r = mid - 1;
  2. while (l < r); l = mid + 1; r = mid - 1;
  3. while (l < r); l = mid + 1; r = mid;
  4. while (l < r - 1); l = mid; r = mid;

  • l <= r 时, r = mid - 1是合法的,r = mid会陷入死循环

比如针对数组0,1,2,3,4,5, target = 3以下代码

1
2
3
4
5
6
7
while (l <= r) { 
int mid = l + (r - l) / 2;
if (vec[mid] >= target)
r = mid;
else if (vec[mid] < target)
l = mid + 1;
}

l = 3``r = 3时陷入死循环


  • l < r时, r = mid是合法的。 l = mid会陷入死循环

比如针对数组0,1,2,3,4,5, target = 3以下代码

1
2
3
4
5
6
7
while (l < r) { 
int mid = l + (r - l) / 2;
if (vec[mid] <= target)
l = mid;
else if (vec[mid] < target)
r = mid;
}

l = 3``r = 3时陷入死循环


总结

写code时往往需要根据需求组合 == < >三种符号

个人推荐写法:

通常情况下都可以while (l < r) , l = mid + 1, r = mid组合使用

当需要使用 l = midwhile (l < r - 1), l = mid, r = mid 最后再检测 l,r哪个一个为需要的解

在sorted数组中,返回第一个不小于target的元素的index

1
2
3
4
5
6
7
8
9
10
11
int lower_bound(vector<int>& vec, int target) {
int l = 0, r = vec.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (target <= vec[mid])
r = mid;
else
l = mid + 1;
}
return vec[l] >= target ? l : -1;
}
  1. vec[mid] == target -> r = mid
  2. vec[mid] < target -> l = mid + 1
  3. vec[mid] > target -> r = mid - 1

所以

1
2
3
4
if (vec[mid] >= target)
r = mid;
else
l = mid + 1;

在sorted数组中,返回第一个大于target的元素的index

1
2
3
4
5
6
7
8
9
10
11
int upper_bound(vector<int>& vec, int target) {
int l = 0, r = vec.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (vec[mid] <= target)
l = mid + 1;
else
r = mid;
}
return vec[l] > target ? l : -1;
}
  1. vec[mid] == target -> l = mid + 1
  2. vec[mid] < target -> l = mid + 1
  3. vec[mid] > target -> r = mid

所以

1
2
3
4
if (vec[mid] <= target)
l = mid + 1;
else
r = mid;

在sorted数组中,返回第一个target元素的index

1
2
3
4
5
6
7
8
9
10
11
int search(vector<int>& vec, int target) {
int l = 0, r = vec.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (vec[mid] >= target)
r = mid;
else
l = mid + 1;
}
return vec[l] == target ? l : -1;
}
  1. vec[mid] == target -> r = mid
  2. vec[mid] > target -> r = mid - 1
  3. vec[mid] < target -> l = mid + 1

在sorted数组中,返回最后一个target元素的index

1
2
3
4
5
6
7
8
9
10
11
int search(vector<int>& vec, int target) {
int l = 0, r = vec.size() - 1;
while (l < r - 1) {
int mid = l + (r - l) / 2;
if (vec[mid] <= target)
l = mid;
else
r = mid - 1;
}
return vec[r] == target ? r : (vec[l] == target ? l : -1);
}
  1. vec[mid] == target -> l = mid
  2. vec[mid] > target -> r = mid - 1
  3. vec[mid] < target -> l = mid + 1

需要注意的是,因为l = mid,所以 while (l < r - 1)以避免死循环


Binary Search in Rotated Array

I met this question in an interview.
Well, you can definitely find a more elegent solution than this one.
The thought is simple, find the indent first. Then, you can transfer this question into typical binary search.

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
class Solution {
public:
int search(vector<int>& nums, int target) {
int indent = 0, n = nums.size(), l = 0, r = n - 1;
if (!n)
return -1;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[l] < nums[r]) {
break;
} else {
if (nums[mid] >= nums[l]) {
l = mid + 1;
} else {
r = mid;
}
}
}
indent = l;
l = 0, r = n - 1;
while (l < r) {
int mid = (l + (r - l) / 2 + indent) % n;
if (nums[mid] > target)
r = l + (r - l) / 2 - 1;
else if (nums[mid] < target)
l = l + (r - l) / 2 + 1;
else
return mid;
}
return nums[(l + indent) % n] == target ? ((l + indent) % n) : -1;
}
};