加载中…
应用场景：有序数组查找 · 查找边界 · 二分答案
交互式动画演示，可调整参数并单步执行。
全屏打开二分查找（Binary Search） 是一种在有序数组中查找目标元素的搜索算法。它通过每一步将搜索区间缩小一半，达到 O(log n) 的时间复杂度。
它是分治思想最纯粹的体现：每次排除一半。
graph TD
S[候选区间 L..R] --> M[取中点 mid]
M --> C{arr[mid] ? target}
C -->|==| F[找到]
C -->|<|R[收缩左界 L=mid+1]
C -->|>|L[收缩右界 R=mid-1]
R --> M
L --> M
假设在有序数组 arr[0..n-1] 中查找 target：
mid。arr[mid] == target，查找成功。arr[mid] < target，目标在右半边。arr[mid] > target，目标在左半边。| 查找方法 | 时间复杂度 | n=1e6 比较次数 |
|---|---|---|
| 线性查找 | O(n) | 1,000,000 |
| 二分查找 | O(log n) | 20 |
每比较一次，区间大小减半。n 次比较能定位到 2ⁿ 个元素中的任意位置。
public static int search(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}public static int searchRecursive(int[] arr, int target, int left, int right) {
if (left > right) return -1;
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) return searchRecursive(arr, target, mid + 1, right);
return searchRecursive(arr, target, left, mid - 1);
}模板化是面试拿分的关键。以下四个模板覆盖 90% 二分题。
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) left = mid + 1;
else right = mid;
}
return left; // 第一个 >= target 的位置while (left < right) {
int mid = left + (right - left + 1) / 2; // 上中点
if (arr[mid] > target) right = mid - 1;
else left = mid;
}
return left;while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) left = mid + 1;
else right = mid;
}
return left; // 插入后仍有序这是面试最常栽的地方。
left <= right vs left < right| 条件 | 区间定义 | 退出时 |
|---|---|---|
left <= right | 闭区间 [left, right] | left > right，区间为空 |
left < right | 半开区间 [left, right) | left == right，区间还有 1 个 |
| 写法 | 行为 |
|---|---|
(left + right) / 2 | 整数可能溢出 |
left + (right - left) / 2 | ✅ 推荐，下中点 |
left + (right - left + 1) / 2 | 上中点（用于模板 3） |
mid 偏向对结果的影响心法：
right = mid时用下中点；left = mid时用上中点。
把"求最优解"转化为"判断某值是否可行"，再用二分搜索可行解。
经典例：分割数组的最大值（LeetCode 410）。
public int splitArray(int[] nums, int m) {
int lo = Arrays.stream(nums).max().getAsInt();
int hi = Arrays.stream(nums).sum();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (canSplit(nums, m, mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
private boolean canSplit(int[] nums, int m, int max) {
int sum = 0, count = 1;
for (int x : nums) {
if (sum + x > max) { sum = x; count++; }
else sum += x;
}
return count <= m;
}识别特征：
[lo, hi]）。| 题目 | 模板 | 关键 |
|---|---|---|
| 搜索插入位置 | 标准 | 返回 left |
| 第一个错误版本 | 左边界 | 返回 left |
| 寻找峰值 | 局部 | 比较 mid 与 mid+1 |
| 旋转排序数组搜索 | 分类讨论 | 先判断哪半有序 |
| 寻找两个正序数组中位数 | 转换 | 二分较短数组 |
| 分割数组的最大值 | 二分答案 | canSplit 判可行性 |
left < right 时必须确保 mid 偏向某一边。// 在循环里打印中间状态
while (left <= right) {
int mid = left + (right - left) / 2;
System.out.printf("left=%d right=%d mid=%d arr[mid]=%d%n", left, right, mid, arr[mid]);
...
}或者手动跑 n=3 的小数组，验证每一步 left/right/mid 的变化。
| 维度 | 复杂度 |
|---|---|
| 时间 | O(log n) |
| 空间 | O(1)（迭代）/ O(log n)（递归栈） |
| 难度 | 题目 | 模板 |
|---|---|---|
| 🟢 | 二分查找 | 标准 |
| 🟢 | 搜索插入位置 | 标准 |
| 🟢 | 第一个错误版本 | 左边界 |
| 🟡 | 在排序数组中查找元素的第一个和最后一个位置 | 左 + 右边界 |
| 🟡 | 搜索旋转排序数组 | 分类讨论 |
| 🟡 | 寻找峰值 | 局部 |
| 🟡 | 寻找比目标字母大的最小字母 | 左边界 |
| 🟠 | 分割数组的最大值 | 二分答案 |
| 🟠 | 制作 m 束花所需的最少天数 | 二分答案 |
| 🔴 | 寻找两个正序数组的中位数 | 复杂二分 |
二分不难，模板固定，难的是"识别出要用二分"。
看到"有序 + 查找 + O(log n)"三个关键词，99% 是二分题。
看到"最大值最小 / 最小值最大"想二分答案。
public static int search(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}