二分查找的魔鬼细节：5 道 LeetCode 题踩坑实录

文章目录

• 二分查找的魔鬼细节：5 道 LeetCode 题踩坑实录
• • 一、流派一：排除法 — 标准查找
  • • LeetCode 35：搜索插入位置
    • LeetCode 34：在排序数组中查找第一个和最后一个位置
    • LeetCode 74：搜索二维矩阵
  • 二、流派二：收敛法 — 保留候选
  • • LeetCode 153：寻找旋转排序数组中的最小值
    • LeetCode 162：寻找峰值
    • LeetCode 278：第一个错误的版本
  • 三、流派混合：旋转数组搜 target（LeetCode 33）
  • 四、两个流派对比
  • 五、边界判断：二分最容易炸的地方
  • 总结

二分查找的魔鬼细节：5 道 LeetCode 题踩坑实录

你以为二分查找就是 while (l <= r) 然后 return mid？我刷完 5 道题，发现边界、返回值、循环条件，每一条都能出 bug。

这篇文章从一个标准模板出发，覆盖 LeetCode 35 / 34 / 74 / 33 / 153 / 162 六道题，把二分查找的写法分成两个流派，一次性讲清楚。

一、流派一：排除法 — 标准查找

适用场景：给定 target，找到返回下标，找不到返回 -1。

int binarySearch(int[] nums, int target) {
int l = 0, r = nums.length – 1;
while (l <= r) {
int mid = l + (r – l) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) l = mid + 1;
else r = mid – 1;
}
return –1;
}

三条铁律：

• while (l <= r)：mid 确定不是答案就彻底排除，两边都 mid ± 1
• 区间始终是 [l, r]，l == r 时还有一个元素要检查
• 循环结束 l > r，说明找不到

一句话：mid 不是答案，跳过。配 while (l <= r)。

LeetCode 35：搜索插入位置

要找第一个 >= target 的位置。把标准模板改一行：

int lowerBound(int[] nums, int target) {
int l = 0, r = nums.length – 1;
while (l <= r) {
int mid = l + (r – l) / 2;
if (nums[mid] < target) l = mid + 1;
else r = mid – 1;
}
return l; // 第一个 >= target
}

循环结束 l > r，通常 r = l – 1。此时 l 指向第一个 >= target 的位置，r 指向最后一个 < target 的位置。

记住这个表，34 题直接秒。

LeetCode 34：在排序数组中查找第一个和最后一个位置

分两步：找左边界（第一个 >= target），找右边界（最后一个 <= target）。

class Solution {
public int[] searchRange(int[] nums, int target) {
int first = findFirst(nums, target);
if (first == –1) return new int[]{–1, –1};
int last = findLast(nums, target);
return new int[]{first, last};
}

int findFirst(int[] nums, int target) {
int l = 0, r = nums.length – 1;
while (l <= r) {
int mid = l + (r – l) / 2;
if (nums[mid] < target) l = mid + 1;
else r = mid – 1;
}
// l 可能越右界（target 比所有数都大）
if (l == nums.length || nums[l] != target) return –1;
return l;
}

int findLast(int[] nums, int target) {
int l = 0, r = nums.length – 1;
while (l <= r) {
int mid = l + (r – l) / 2;
if (nums[mid] <= target) l = mid + 1;
else r = mid – 1;
}
// r 可能越左界（target 比所有数都小）
if (r < 0 || nums[r] != target) return –1;
return r;
}
}

关键：findFirst 返回 l，findLast 返回 r。两个函数只有条件里的 = 不一样。

LeetCode 74：搜索二维矩阵

每行递增，且下一行首元素 > 上一行末元素。当成一维数组二分：

class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int l = 0, r = m * n – 1;
while (l <= r) {
int mid = l + (r – l) / 2;
int val = matrix[mid / n][mid % n];
if (val == target) return true;
else if (val < target) l = mid + 1;
else r = mid – 1;
}
return false;
}
}

mid / n 是行，mid % n 是列。转换完就是标准二分。

二、流派二：收敛法 — 保留候选

适用场景：没给 target，要找极值或边界。mid 满足条件时，它自己可能就是答案。

int findMin(int[] nums) {
int l = 0, r = nums.length – 1;
while (l < r) {
int mid = l + (r – l) / 2;
if (nums[mid] > nums[r]) l = mid + 1;
else r = mid; // mid 可能是答案，不跳过
}
return nums[l]; // l == r → 答案
}

三条铁律：

• while (l < r)：因为 r = mid，l <= r 会死循环
• 只跳过确定不是答案的那半边，保留可能是答案的 mid
• 循环结束 l == r，这就是答案

一句话：mid 可能是答案，保留。配 while (l < r)。

为什么只能 r = mid 不能 l = mid？

mid = l + (r – l) / 2 是向下取整。当 r = l + 1 时，mid = l。如果写 l = mid，l 不动，死循环。r = mid 则一定会收缩，因为 mid 永远 < r。

如果你非要 l = mid，就把 mid 改成向上取整：mid = l + (r – l + 1) / 2。

LeetCode 153：寻找旋转排序数组中的最小值

class Solution {
public int findMin(int[] nums) {
int l = 0, r = nums.length – 1;
while (l < r) {
int mid = l + (r – l) / 2;
if (nums[mid] > nums[r]) l = mid + 1;
else r = mid;
}
return nums[l];
}
}

比较对象必须是 nums[r]，不能是 nums[l]。反例：[1,2,3,4,5] 没有旋转，nums[mid]=3 > nums[l]=1 会跳过最小值下标 0。

LeetCode 162：寻找峰值

class Solution {
public int findPeakElement(int[] nums) {
int l = 0, r = nums.length – 1;
while (l < r) {
int mid = l + (r – l) / 2;
if (nums[mid] > nums[mid + 1]) r = mid; // mid 可能是峰值
else l = mid + 1;
}
return l;
}
}

LeetCode 278：第一个错误的版本

public int firstBadVersion(int n) {
int l = 1, r = n;
while (l < r) {
int mid = l + (r – l) / 2;
if (isBadVersion(mid)) r = mid; // mid 就是 bad，可能是第一个
else l = mid + 1;
}
return l;
}

三、流派混合：旋转数组搜 target（LeetCode 33）

这道题需要两个流派配合：先收敛法找旋转点，再排除法搜 target。

class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length – 1;

// 直接在一次二分里判断：哪半有序，target 在不在里面
while (l <= r) {
int mid = l + (r – l) / 2;
if (nums[mid] == target) return mid;

if (nums[l] <= nums[mid]) { // 左半有序
if (nums[l] <= target && target < nums[mid]) r = mid – 1;
else l = mid + 1;
} else { // 右半有序
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid – 1;
}
}
return –1;
}
}

三个 = 号一个都不能丢：nums[l] <= nums[mid] 处理 l == mid 的情况；nums[l] <= target 和 target <= nums[r] 处理 target 在边界的情况。

四、两个流派对比

五、边界判断：二分最容易炸的地方

二分返回值当数组下标用时，有 3 种越界可能：

• return l → l 可能 = n（target > 最大值）
• return r → r 可能 = -1（target < 最小值）
• 旋转数组里拿返回值去访问数组——先判 idx >= 0 && idx < n

统一防御写法：

int idx = binarySearch(nums, target);
if (idx < 0 || idx >= nums.length) return –1; // 或 return false

总结

二分查找代码短，但边界条件一个都不能省。搞清两个流派，六道题一套模板搞定。