前提：数组有序
每次排除一半，时间复杂度 O(log n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int binarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1; // 右闭
while (left <= right) { // <= 因为是闭区间
int mid = left + (right - left) / 2; // 防溢出，不用 (l+r)/2
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1; // mid 已经看过了，+1
} else {
right = mid - 1; // mid 已经看过了，-1
}
}
return -1; // 没找到
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int binarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size(); // 右开
while (left < right) { // < 因为开区间不包含 right
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid; // 右开，right 本身不包含，所以不用 -1
}
}
return -1;
}
|
推荐用左闭右闭，逻辑更直观，不容易错。
1
2
3
4
5
6
7
8
9
10
11
12
| int lowerBound(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid; // 找左边界，往左边缩
} else {
left = mid + 1;
}
}
return left; // left == right，就是第一个 >= target 的位置
}
|
判断是否存在： 返回值 < nums.size() && nums[left] == target
1
2
3
4
5
6
7
8
9
10
11
12
| int upperBound(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1; // 找右边界，往右边扩
} else {
right = mid;
}
}
return left - 1; // 最后一个 <= target 的位置
}
|
| 目标 | 条件 | 返回 |
|---|
| 是否存在 target | == 返回 mid | 下标 或 -1 |
| 第一个 >= target（左边界） | >= 时 right=mid | left |
| 第一个 > target（upper_bound） | > 时 right=mid | left |
| 最后一个 <= target | <= 时 left=mid+1 | left - 1 |
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include <algorithm>
// 第一个 >= target 的迭代器
auto it1 = lower_bound(nums.begin(), nums.end(), target);
// 第一个 > target 的迭代器
auto it2 = upper_bound(nums.begin(), nums.end(), target);
// 等于 target 的范围 [first, last)
auto range = equal_range(nums.begin(), nums.end(), target);
// target 出现的次数
int cnt = upper_bound(v.begin(), v.end(), x) - lower_bound(v.begin(), v.end(), x);
|
找第一个 >= target 的位置，就是插入位置。
分别找左边界和右边界。
答案有单调性时，对答案二分：
- 「使…最大值最小」→ 二分答案，check 是否可行
- 「使…最小值最大」→ 二分答案，check 是否可行
部分有序，判断哪一半是有序的，再决定搜哪边。
- 确定区间形式：左闭右闭还是左闭右开（推荐左闭右闭）
- 确定循环条件：
<= 还是 < - 确定 mid 更新方式：left = mid+1 / right = mid-1 还是别的
- 考虑边界情况：target 比所有都小 / 都大 / 不存在
- mid 溢出：用
left + (right - left) / 2，不用 (left + right) / 2 - 死循环：left = mid 时容易死循环，mid 要向上取整
left + (right - left + 1) / 2 - 边界判断：循环结束后记得判断是否越界
- 区间一致性：全程保持区间定义一致，别一会儿闭一会儿开