加载中…
应用场景：第一个/最后一个满足条件的位置 · 旋转数组
交互式动画演示，可调整参数并单步执行。
全屏打开二分答案不是在一个数组里找某个值，而是在答案的可能范围内二分，通过一个验证函数（check）判断当前猜测是否可行，从而逐步缩小答案范围。
核心条件：答案具有单调性——如果 x 可行，那么所有 ≤ x（或 ≥ x）的值也可行。
graph LR
A[答案范围 lo..hi] --> B[取 mid]
B --> C{check mid 可行?}
C -->|是| D[hi = mid 或记录答案]
C -->|否| E[lo = mid + 1]
D --> A
E --> A
int lo = minVal, hi = maxVal;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (check(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;int lo = minVal, hi = maxVal;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (check(mid)) {
lo = mid;
} else {
hi = mid - 1;
}
}
return lo;防死循环：当
lo + 1 == hi时，若mid = lo（不加 1），且 check 为 true →lo = mid = lo，死循环。
问题：将数组分成 k 段，使各段之和的最大值最小。
public int splitArray(int[] nums, int k) {
int lo = 0, hi = 0;
for (int x : nums) { lo = Math.max(lo, x); hi += x; }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (canSplit(nums, k, mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
private boolean canSplit(int[] nums, int k, int maxSum) {
int count = 1, curSum = 0;
for (int x : nums) {
if (curSum + x > maxSum) { count++; curSum = 0; }
curSum += x;
}
return count <= k;
}问题：求最低运载能力，使所有包裹在 D 天内送达。
public 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;
}
private boolean canShip(int[] weights, int days, int capacity) {
int need = 1, cur = 0;
for (int w : weights) {
if (cur + w > capacity) { need++; cur = 0; }
cur += w;
}
return need <= days;
}public int mySqrt(int x) {
if (x < 2) return x;
int lo = 1, hi = x / 2;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (mid <= x / mid) lo = mid;
else hi = mid - 1;
}
return lo;
}public int minEatingSpeed(int[] piles, int h) {
int lo = 1, hi = 0;
for (int p : piles) hi = Math.max(hi, p);
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (canFinish(piles, h, mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
private boolean canFinish(int[] piles, int h, int speed) {
int hours = 0;
for (int p : piles) hours += (p + speed - 1) / speed;
return hours <= h;
}看到以下关键词，考虑二分答案：
| 信号 | 示例 |
|---|---|
| "最大值最小" / "最小值最大" | 分割数组最大值最小化 |
| "最少/最多需要多少" | 最少运载能力 |
| "能否在 X 内完成" | D 天内送达 |
| 答案有明确上下界 | 速度 ∈ [1, max] |
| 验证某个答案是否可行很容易 | check 函数 O(n) |
| 维度 | 二分查找 | 二分答案 |
|---|---|---|
| 搜索对象 | 数组中的元素 | 答案的数值范围 |
| 前提 | 数组有序 | 答案具有单调性 |
| check | 比较大小 | 自定义验证函数 |
| 典型题 | 查找目标值 | 分割数组、运载能力 |
| 陷阱 | 解决 |
|---|---|
| 死循环 | 右边界模板 mid 要 +1 |
| 整数溢出 | mid = lo + (hi - lo) / 2 |
| 边界遗漏 | 先验证 lo 和 hi 是否可行 |
| check 方向搞反 | 明确"可行时缩哪边" |
| 浮点二分 | 用 while (hi - lo > 1e-7) 控制精度 |
double lo = 0, hi = 1e9;
while (hi - lo > 1e-7) {
double mid = (lo + hi) / 2;
if (check(mid)) hi = mid;
else lo = mid;
}
return lo;public int mySqrt(int x) {
if (x < 2) return x;
int lo = 1, hi = x / 2;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (mid <= x / mid) lo = mid;
else hi = mid - 1;
}
return lo;
}