二分算法
二分的本质是边界，整个区间可以一分为二，左半边满足某性质，右半边不满足某性质，二分就是用来寻找这个边界的方法。
整数二分
做法：
- 情况一：找到
mid = (l + r + 1) / 2
if (check(mid)):
- true 边界点在 [mid, r]这个范围内，更新方式：
l = mid
- false 边界点在[l, mid - 1]这个范围内，更新方式
r = mid - 1
- 情况二：找到
mid = (l + r) / 2
if (check(mid)):
- true 边界点在 [l, mid]这个范围内，更新方式：
r = mid
- false 边界点在[mid + 1, r]这个范围内，更新方式
l = mid + 1
拿到题目：
先写check函数，如果true的时候是l = mid则补上+1，如果true的时候是r = mid则不加一
模版
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
48
49
50
|
// 普通二分查找int
int binarySearch(const vector<int>& nums, int target) {
int left = 0, right = (int)nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
// 更通用的二分模板
// LeetCode34 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ans;
// 开始位置（lower_bound）：查询第一个>=target的数
// 范围 [0 .. n-1 ] + [n表示不存在]
int left = 0, right = nums.size();
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] >= target)
right = mid;
else
left = mid + 1;
}
ans.push_back(right); //第一个>=target的数的下标（不存在为n）
// 结束位置：查询最后一个<=target的数
// 范围 [-1表示不存在] + [0 .. n-1 ]
left = -1, right = nums.size() - 1;
while (left < right) {
int mid = (left + right + 1) / 2;
if (nums[mid] <= target)
left = mid;
else
right = mid - 1;
}
ans.push_back(right);
//最后一个<=target的数（不存在为-1）
// target出现在[ans[0], ans[1]]
if (ans[0] > ans[1])
ans = {-1, -1};
return ans;
}
};
|
浮点数二分
跟整数二分思路一致，但不用区分是否+1，没有边界问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
// 实数二分模板
// ans = realSqrt(x)
// 如果要求4位小数，就多算2~4位，到1e-6或1e-8，保证精确
double realSqrt(double x, double eps = 1e-6) {
double left = 0, right = max(x, 1.0);
while (right - left > eps) {
double mid = (left + right) / 2;
if (mid * mid <= x) {
left = mid;
} else {
right = mid;
}
}
return right;
}
|
Sugar