二分法 Binary Search
应用二分法的前提条件
搜索空间单调！
\[
\displaylines{
i < j \Rightarrow test(i) \rightarrow test(j)
}
\]
分类（根据搜索目标）
-
单值
* 左边界int binary_search(int[] nums, int target) { int left = 0, right = nums.length - 1; while(left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if(nums[mid] == target) { // 直接返回 return mid; } } // 直接返回 return -1; }* 右边界int left_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { // 别返回，锁定左侧边界 right = mid - 1; } } // 最后要检查 left 越界的情况 if (left >= nums.length || nums[left] != target) return -1; return left; } // simplif version bool test(int m) { // ... 1 2 [ 3 4 ... // false [ true if (OK(m)) return true; else: return false; } int left_bound() { int l = L, r = R; while (l <= r) { int m = (l + r) / 2; if (test(m)) r = m - 1; else l = m + 1; } return l; }* STD function for simple usage:int right_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { // 别返回，锁定右侧边界 left = mid + 1; } } // 最后要检查 right 越界的情况 if (right < 0 || nums[right] != target) return -1; return right; } // simplified version bool test(int m) { // ... 1 2 ] 3 4 ... // true ] false if (OK(m)) return true; else: return false; } int right_bound() { int l = L, r = R; while (l <= r) { int m = (l + r) / 2; if (test(m)) l = m + 1; else r = m - 1; } return r; }#include <algorithm> // lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个**大于或等于**num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 // upper_bound(begin,end,num)：从数组的begin位置到end-1位置二分查找第一个**大于**num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 // small --> large sort(v.begin(), v.end()); int l = lower_bound(v.begin(), v.end(), x) - v.begin(); int r = upper_bound(v.begin(), v.end(), x) - v.begin(); // large --> small sort(v.begin(), v.end(), greater<int>()); int l = lower_bound(v.begin(), v.end(), x, greater<int>()) - v.begin(); int r = upper_bound(v.begin(), v.end(), x, greater<int>()) - v.begin(); // remember to check the boundary! // e.g., find the nearest number to x in v. int ans; int i = lower_bound(v.begin(), v.end(), x) ; if (i == 0) { ans = v[i]; } else if (i == v.size()) { ans = v[i-1]; } else { if (abs(v[i] - x) < abs(v[i-1] - x)) ans = v[i]; else ans = v[i-1]; }
浮点二分
需要指定精度eps，但不需要修改边界。
float mysqrt(float x, float eps=1e-4) {
float l = 0, r = x;
while (r - l >= eps) {
float m = (l + r) / 2;
if (m * m - x > eps) r = m;
else l = m;
}
return l;
}
题目
174 地下城游戏
正向动态规划不现实，需要记录抵达时最大生命与途中最小生命，不满足最优子结构。
但是在给定生命时，可以通过正向动态规划得到抵达时的最大生命。
存活是生命的单调函数，问题转变为对左边界（最小需要生命）的二分搜索。
从 +inf开始搜索，问题保证有解，故不需要越界检查。
class Solution {
public:
bool test(vector<vector<int>>& dungeon, int m) {
int M = dungeon.size();
int N = dungeon[0].size();
vector<vector<int>> dp(M + 1, vector<int>(N + 1, -0x3f3f3f));
dp[0][1] = dp[1][0] = m;
for (int i = 1; i <= M; i++) {
for (int j = 1; j <= N; j++) {
int val = max(dp[i-1][j], dp[i][j-1]) + dungeon[i-1][j-1];
if (val <= 0) continue;
else dp[i][j] = val;
}
}
return dp[M][N] > 0;
}
int calculateMinimumHP(vector<vector<int>>& dungeon) {
// [l, r] binary search, left bound
int l = 1, r = 0x3f3f3f3f;
while (l <= r) {
int m = l + (r - l) / 2;
// m survives
if (test(dungeon, m)) r = m - 1;
else l = m + 1;
}
return l;
}
};
正方形矩阵边长
前缀和 + 右边界搜索。
class Solution {
public:
bool test(vector<vector<int>>& s, int k, int threshold){
int m = s.size();
int n = s[0].size();
for (int i = 0; i < m - k; i++) {
for (int j = 0; j < n - k; j++) {
if (s[i+k][j+k] - s[i+k][j] - s[i][j+k] + s[i][j] <= threshold){
return true;
}
}
}
return false;
}
int maxSideLength(vector<vector<int>>& mat, int threshold) {
int m = mat.size();
if (m == 0) return 0;
int n = mat[0].size();
if (n == 0) return 0;
// prefix sum
vector<vector<int>> s(m+1, vector<int>(n+1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + mat[i-1][j-1];
}
}
// bs right bound []
int l = 1, r = max(m, n);
while (l <= r) {
int m = (l + r) / 2;
if (test(s, m, threshold)) l = m + 1;
else r = m - 1;
}
return r;
}
};
162寻找峰值
边界判定十分麻烦。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
// size == 1
if (nums.size() == 1) return 0;
int l = 0, r = nums.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
// border
if (m == 0) return nums[m] > nums[m + 1] ? m : m + 1;
if (m == nums.size() - 1) return nums[m] > nums[m - 1] ? m : m - 1;
// middle
if (nums[m] > nums[m - 1] && nums[m] > nums[m + 1]) return m;
else if (nums[m] <= nums[m - 1]) r = m - 1;
else if (nums[m] <= nums[m + 1]) l = m + 1;
}
return -1; // never reach here.
}
};
可移除字符的最大数目
子序列判断要用双指针法！
class Solution {
public:
// lr pointer for O(m+n) subsequence check
bool check(int m, string& s, string& p, vector<int>& v) {
int i = 0, j = 0;
while (i < s.size() && j < p.size()) {
if (s[i] == p[j] && v[i] > m) {
i++; j++;
} else {
i++;
}
}
return (j == p.size());
}
int maximumRemovals(string s, string p, vector<int>& removable) {
// for O(1) check if a char is removed at time t.
vector<int> v(s.size(), 0x7fffffff);
for (int i = 0; i < removable.size(); i++) {
v[removable[i]] = i;
}
// binary search for left border
int l = 0, r = removable.size() - 1;
while (l <= r) {
int m = (l + r) / 2;
if (check(m, s, p, v)) l = m + 1;
else r = m - 1;
}
return r + 1;
}
};