算法复盘——二分查找
一、思路
满足单调性 → 二分答案 → check 贪心验证 → 求最小 / 最大值
二、例题
1. 跳石头
P2678 [NOIP 2015 提高组] 跳石头 - 洛谷
题目核心：
1、起点0，终点L，中间有N块石头，位置已由小到大排序好
2、最多移走M块石头
3、目标是将最短跳跃的距离最大化
分析：
为何使用二分算法？
1、答案具有单调性：要求的距离越短所要移动的石头就越少；距离越远要求移动的石头也就越多。
2、从而构成了二段性，二分就是来找这个分段点的，即能否在移走 ≤M 块石头的前提下，让所有跳跃距离都 ≥mid
可行 可行 … 可行 | 不可行 不可行 …代码实现：
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 5e4 + 10; int n, L, a[N], m; int check(int mid) { int tmp = 0; for (int i = 0; i <= n; i++) { int j = i + 1; while(j <= n && a[j] - a[i] < mid) j++; //站在i往j跳 tmp += (j - i - 1); i = j - 1; } return tmp; } signed main() { cin >> L >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; a[++n] = L; int l = 1, r = L; while(l < r) { int mid = (l + r + 1) >> 1; if(check(mid) <= m) l = mid; else r = mid - 1; } cout << l<< endl; return 0; }2. 木材加工
P2440 木材加工 - 洛谷
题目核心：
1、一共n块原木，每根原木长Li，要切割最终得到k段
2、目标是让最小的段尽可能大
分析：
单调性：长度越长，段数越少
代码实现：
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 10; int n, k, a[N], lmax; int check(int mid) { int tmp = 0; for(int i = 1; i <= n; i++) tmp += a[i] / mid; return tmp; } signed main() { cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; lmax = max(lmax, a[i]); } if (check(1) < k) { cout << 0 << endl; return 0; } int l = 1, r = lmax; while(l < r) { int mid = (l + r + 1) >> 1; if(check(mid) >= k) l = mid; else r = mid - 1; } cout << l << endl; return 0; }3. 分割数组最大值
410. 分割数组的最大值 - 力扣（LeetCode）
题目核心：
1、一个数组，要进行连续的分割，分割成k段
2、目标是让每段的和尽可能的小
分析：
单调性：候选值（每段和的上限）越大，每段所放入的元素就越多，分的段数就越少；反之亦然
代码实现：
class Solution { public: int splitArray(vector<int>& nums, int k) { // 左边界：数组最大值，右边界：数组总和 int left = *max_element(nums.begin(), nums.end()); int right = accumulate(nums.begin(), nums.end(), 0); // 二分查找 while (left < right) { int mid = left + (right - left) / 2; // 判断最大和为 mid 时，是否能分成 <=k 段 if (check(nums, mid) <= k) { // 可以满足 → 还可优化 → 尝试更小mid right = mid; } else { // 不满足 → 需要更大的值 left = mid + 1; } } return left; } int check(vector<int>& nums, int maxSum) { int count = 1; // 初始段数为 1 int curSum = 0; // 当前段的和 for (int num : nums) { curSum += num; if (curSum > maxSum) { // 超过上限，必须新开一段 curSum = num; count++; } } return count; } };4.进击的奶牛
P1824 [USACO05FEB] 进击的奶牛 Aggressive Cows G - 洛谷
代码实现：
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, m, a[N]; int check(int mid) { int cnt = 1; int last = a[1]; for(int i = 2; i <= n; i++) { if(a[i] - last >= mid) { cnt++; last = a[i]; } } return cnt; } signed main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + 1 + n); int l = 1, r = a[n] - a[1]; while(l < r) { int mid = (l + r + 1) / 2; if(check(mid) >= m) l = mid; else r = mid - 1; } cout << l << endl; return 0; }5.数列分段
P1182 数列分段 Section II - 洛谷
代码实现：
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 10; int n, m; vector <int> a(N); int check(int mid) { int cnt = 1; int sum = 0; for(int i = 1; i <= n; i++) { sum += a[i]; if(sum > mid) { sum = a[i]; cnt++; } } return cnt; } signed main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; int l = *max_element(a.begin() + 1, a.begin() + 1 + n); int r = accumulate(a.begin() + 1, a.begin() + 1 + n, 0LL); while(l < r) { int mid = l + (r - l) / 2; if(check(mid) <= m) r = mid; else l = mid + 1; } cout << l << endl; }