首先了解C++中存在于头文件<algorithm>两个库函数：lower_bound和upper_bound lower_bound(start, end, val)返回在[start, end)中找到第一个大于等于val的位置 upper_bound(start, end, val)返回在[start, end)中找到第一个大于val的位置
只有一个等号的区别，以lower_bound为例，当v[mid]小于x时，left肯定要取mid+1，否则，right=mid，right一定符合, 让left不断逼近right
#include <iostream> #include <vector> using namespace std; int lower_bound(vector<int>& v, int left, int right, int x){ while(left < right){ int mid = (left + right) / 2; if(v[mid] < x) left = mid + 1; else right = mid; } return left; } int upper_bound(vector<int>& v, int left, int right, int x){ while(left < right){ int mid = (left + right) / 2; if(v[mid] <= x) left = mid + 1; else right = mid; } return left; } int main() { vector<int> v{1,2,3,4,5,6,6,7,8,9}; cout << lower_bound(v, 0, v.size(), 6); cout << upper_bound(v, 0, v.size(), 6); return 0; }题目链接：410. Split Array Largest Sum 题目解法：Solution with Greedy Algorithm and Binary Search 给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小 由题意，我们可以知道m必定在[max(max(nums), sum(nums)/m), sum(nums)]之间，我们可以先猜一个中间值max，并构造子数组使得每个子数组之和都不超过max，如果我们从小到大取max,得到一个结果组成数组B，则B中一定是[F,F,F,T,T]这种的，越大更容易为True，这种情况我们可以使用二分法找到第一个T，这个T对应的max就是最小的最大值
class Solution { public: bool doable(vector<int>& nums, long long max, int cut){ long acc = 0; for (int &num: nums) { if(num > max) return false; else if(acc + num <= max) acc += num; else { cut--; acc = num; if(cut < 0) return false; } } return true; } int splitArray(vector<int>& nums, int m) { long long left = 0, right = 0; for (int &num : nums) { left = max(left, (long long)num); right += num; } while (left < right) { long long mid = left + (right - left) / 2; if (doable(nums, mid, m - 1)) right = mid; else left = mid + 1; } return left; } };DP解法:dp方程很简单dp[i][j]表示将索引到i的（包括i）数组分解为j个组的最小最大和递推方程为dp[i][j] = min(max(dp[k][j-1], sum[k+1，i]) ），很慢
class Solution { public: int splitArray(vector<int>& nums, int m) { int n = nums.size(); vector<long long> p(n+1); p[0] = 0; for(long i = 1; i <= n; i++) p[i] = p[i-1] + nums[i-1]; // sum[i, j] = p[j+1] - p[i]; vector<vector<long long>> dp(n + 1, vector<long long>(n+1, INT_MAX)); int MAX = 0; for(int i = 0; i < n; i++) { MAX = max(nums[i], MAX); dp[i][1] = p[i+1]; dp[i][i+1] = MAX; } for(int i = 0; i < n; i++){ for(int j = 2; j <= m; j++){ for(int k = j-2; k < i; k++){ dp[i][j] = min(max(dp[k][j-1], p[i+1]- p[k+1]), dp[i][j]); } } } return dp[n-1][m]; } };二维变一维
class Solution { public: int splitArray(vector<int>& nums, int m) { int n = nums.size(); vector<long long> p(n+1); p[0] = 0; for(long i = 1; i <= n; i++) p[i] = p[i-1] + nums[i-1]; // sum[i, j] = p[j+1] - p[i]; vector<long long> dp(n + 1, INT_MAX); int MAX = 0; for(int i = 0; i < n; i++) { dp[i] = p[i+1]; } for(int j = 2; j <= m; j++){ for(int i = n - 1; i >= 0; i--){ dp[i] = INT_MAX; for(int k = j-2; k < i; k++){ dp[i] = min(max(dp[k], p[i+1]- p[k+1]), dp[i]); } } } return dp[n-1]; } };题目链接：718. Maximum Length of Repeated Subarray 题目解法：Github Issue 324. Maximum Length of Repeated Subarray 这题本身很简单，DP的话和LCS差不多，也可以用偏移做，时间复杂度是\(O(n^2)\) 但是值得一提的是二分搜索的解法Binary Search + Rabin Karp + Hash Table, O(N log N), Beats 100% 大致思路是计算每个[0,i]串的hash值，然后计算长度为m的串hash值，判断两个数组中的串的hash是否有重合，如果有重合，增大l=m+1, 如果没有r=m-1，这种做法容易溢出，但思路很好
class Solution { public: int findLength(vector<int>& A, vector<int>& B) { const int P = 19941229; //Rabin-Karp vector<int> hash1(A.size() + 1, 0), hash2(B.size() + 1, 0), p(max(A.size(), B.size()) + 1); int len = max(A.size(), B.size()); p[0] = 1; for (int i = 1; i <= len; i++) p[i] = p[i - 1] * P; for (int i = 1; i <= A.size(); i++) hash1[i] = hash1[i - 1] + A[i - 1] * p[i]; for (int i = 1; i <= B.size(); i++) hash2[i] = hash2[i - 1] + B[i - 1] * p[i]; int l = 1, r = min(A.size(), B.size()); while (l <= r) { //Binary search the answer int m = (l + r) / 2; unordered_set<int> hash; bool ok = false; for (int i = 1; i + m - 1 <= A.size(); i++) //Calculate Rabin-Karp hash for all substring s for the first string of length m, insert into hash table hash.insert((hash1[i + m - 1] - hash1[i - 1]) * p[len - (i + m - 1)]); for (int i = 1; i + m - 1 <= B.size(); i++){ //Calculate Rabin-Karp hash for the second string, query the hash table if (hash.count((hash2[i + m - 1] - hash2[i - 1]) * p[len - (i + m - 1)])) { ok = true; break; } } if (ok) l = m + 1; else r = m - 1; } return r; } };题目链接：174. Dungeon Game 题目解答：A Simple C++ Solution using Binary Search 当然这道题也是一道经典的DP题目采用逆向思维从后往前进行DP，二分法也是不错的方法
class Solution { public: int calculateMinimumHP(vector<vector<int>>& dungeon) { int left = 1; int right = 1; int M = dungeon.size(); int N = dungeon[0].size(); for (int i = 0; i < M; i++) { int val = dungeon[i][0]; if (val < 0) right += (-val); } for (int i = 0; i < N; i++) { int val = dungeon[M-1][i]; if (val < 0) right += (-val); } int dead = INT_MIN / 3; while(left < right){ int mid = (right - left) / 2 + left; vector<vector<int>> h(M + 1, vector<int>(N+1, dead)); h[0][1] = h[1][0] = mid; for(int i = 1; i <= M; i++){ for(int j = 1; j <= N; j++){ h[i][j] = max(h[i-1][j], h[i][j-1]) + dungeon[i-1][j-1]; if(h[i][j] < 1){ h[i][j] = dead; } } } if(h[M][N] > 0){ right = mid; } else { left = mid + 1; } } return left; } };转载于:https://www.cnblogs.com/qbits/p/11233005.html
