二分答案是一种将"求最优值"问题转化为"判定可行性"问题的通用技巧。只要答案具有单调性（满足/不满足某条件），就可以用二分将 O(n) 的搜索优化为 O(log n) 次判定。
一、核心思想
Mermaid · 渲染中（下方为源码）
graph TD
S[答案范围 lo..hi] --> M[取 mid]
M --> C{check mid 可行?}
C -->|是| D[缩小到可行半区]
C -->|否| E[缩小到不可行半区]
D --> M
E --> M
求满足条件的最大/最小值
→ 二分答案 mid
→ 判定 check(mid) 是否可行
→ 根据结果缩小搜索范围
二、模板
求最小满足值（左边界）
int binarySearchMin(int lo, int hi) {
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (check(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}求最大满足值（右边界）
int binarySearchMax(int lo, int hi) {
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (check(mid)) {
lo = mid;
} else {
hi = mid - 1;
}
}
return lo;
}三、经典例题
分割数组的最大值（LeetCode 410）
将数组分成 m 段，使各段和的最大值最小。
int splitArray(int[] nums, int m) {
int lo = 0, hi = 0;
for (int n : nums) { lo = Math.max(lo, n); hi += n; }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (canSplit(nums, m, mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
boolean canSplit(int[] nums, int m, int maxSum) {
int count = 1, curSum = 0;
for (int n : nums) {
if (curSum + n > maxSum) {
count++;
curSum = n;
if (count > m) return false;
} else {
curSum += n;
}
}
return true;
}爱吃香蕉的珂珂（LeetCode 875）
int minEatingSpeed(int[] piles, int h) {
int lo = 1, hi = Arrays.stream(piles).max().getAsInt();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (canFinish(piles, h, mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
boolean canFinish(int[] piles, int h, int speed) {
int hours = 0;
for (int p : piles) hours += (p + speed - 1) / speed;
return hours <= h;
}在 D 天内送达包裹的能力（LeetCode 1011）
int shipWithinDays(int[] weights, int days) {
int lo = 0, hi = 0;
for (int w : weights) { lo = Math.max(lo, w); hi += w; }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (canShip(weights, days, mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}四、适用场景
| 场景 | 判定函数 |
|---|---|
| 最大值最小化 | 能否在限制内完成 |
| 最小值最大化 | 能否满足最低要求 |
| 第 k 小/大 | 有多少个 ≤ mid |
| 浮点精度 | 误差 < ε |
浮点二分
double sqrt(double x) {
double lo = 0, hi = x;
while (hi - lo > 1e-9) {
double mid = (lo + hi) / 2;
if (mid * mid < x) lo = mid;
else hi = mid;
}
return lo;
}五、面试要点
- 确定搜索范围：lo 和 hi 的初始值
- 写 check 函数：判定 mid 是否可行
- 防死循环：求最大值时 mid = lo + (hi-lo+1)/2
- 单调性：答案必须满足"小于某值全不可行，大于某值全可行"
- LeetCode：410、875、1011、4、153、33、69、162