LeetCode Hot 100 二分查找篇 - 每次砍一半，六道题从入门到穿透

哈喽，大家好呀，我是蔚蓝～，今天我们来聊 LeetCode Hot 100 的二分查找。

你查过字典吗？不是手机上那种输入法自动补全，是真的翻一本厚厚的纸质字典。

翻到中间，看一下，字母在左边就翻左边，在右边就翻右边。每次把搜索范围砍掉一半。

这就是二分查找。

听起来简单到不值一提对吧？但 Hot 100 里选了六道二分的题，从 Easy 一路杀到 Hard。你会发现，同样是「每次砍一半」，切的姿势可以天差地别。

今天我把这六道题拆开，从标准模板到双数组切割，逐级通关。

一、LC35 搜索插入位置 - 先把标准模板焊死

这是二分查找的「Hello World」。

给一个有序数组和一个目标值，找到了返回下标，找不到就返回它该插入的位置。

核心问题来了：找不到的时候，循环结束那一刻，l 和 r 分别指向哪里？

l 指向第一个大于等于 target 的位置，r 指向最后一个小于 target 的位置。所以 l 刚好就是插入点。

这不是巧合。是循环不变量决定的 —— 整个过程里，l 左边的元素始终小于 target，r 右边的元素始终大于 target。当 l > r 的时候，l 就是那个分界线。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2; // 防溢出，等价于 (l+r)/2
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l; // l 就是第一个 >= target 的位置
    }
}

避坑：

  • 不要用 (l + r) / 2，数据量大了会溢出
  • 循环条件是 l <= r，不是 l < r，否则会漏检
  • 找不到时返回 l，不是 r，也不是 -1

这三个坑，你踩过几个？我当年三个全踩了。

二、LC74 搜索二维矩阵 - 展平了就是一维

给你一个矩阵，每行递增，每行第一个数比上一行最后一个数大。问 target 在不在里面。

看到「每行第一个数比上一行最后一个数大」这个条件，你就该反应过来：按行展开，这不就是一个严格递增的一维数组吗？

把二维坐标映射成一维下标：row = idx / n, col = idx % n。然后就是标准的二分查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int R = matrix.length, C = matrix[0].length;
        int l = 0, r = R * C - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            int val = matrix[mid / C][mid % C]; // 一维下标映射到二维坐标
            if (val == target) {
                return true;
            } else if (val < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return false;
    }
}

一眼识别： 只要看到「每行首元素大于上一行尾元素」，立刻想到展平。不用真的开新数组，坐标映射就够了，O(1) 空间。

三、LC34 查找首尾位置 - 一个 lower_bound 走天下

给一个非递减数组，可能有重复元素，找某个值的第一个和最后一个位置。

如果用两次二分，分别找左边界和右边界，代码写起来会重复。这题有一个很优雅的 trick：

右边界 = lower_bound(target + 1) - 1

什么意思？lower_bound(x) 找到第一个大于等于 x 的位置。那么 lower_bound(target + 1) 就是第一个大于 target 的位置，再减一，就是最后一个等于 target 的位置。

一个函数，两次调用，两个边界全搞定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) return new int[]{-1, -1};

        int[] ans = new int[2];
        ans[0] = lowerBound(nums, target);         // 第一个 >= target
        ans[1] = lowerBound(nums, target + 1) - 1; // 最后一个 <= target

        if (ans[0] >= nums.length || nums[ans[0]] != target) {
            return new int[]{-1, -1}; // target 不存在
        }
        return ans;
    }

    // 返回第一个 >= 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; // >= 的情况，mid 可能是答案，但左边可能还有更小的
            }
        }
        return l;
    }
}

避坑： 找到左边界后，必须检查 nums[ans[0]] == target。万一 target 比所有元素都大，lowerBound 返回的是 nums.length，直接越界。

四、LC33 搜索旋转排序数组 - 必有一半有序

数组被旋转过了，比如 [0,1,2,4,5,6,7] 变成了 [4,5,6,7,0,1,2]。要在里面找 target。

乍一看完全无序，没法二分？

但你仔细看，不管从哪里切一刀，左右两半中必定有一半是有序的。

比如 mid = 3，nums = [4,5,6,7,0,1,2]，左半段 [4,5,6,7] 是有序的。那就先判断 target 是不是在这个有序区间里。在的话就在这个区间继续二分，不在就去另一半。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;

            if (nums[left] <= nums[mid]) { // 左半段有序
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1; // target 在左半段
                } else {
                    left = mid + 1;  // target 在右半段
                }
            } else { // 右半段有序
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;  // target 在右半段
                } else {
                    right = mid - 1; // target 在左半段
                }
            }
        }
        return -1;
    }
}

避坑： nums[left] <= nums[mid] 这里必须用 <=，不能用 <。当 left == mid 时（区间只有一两个元素），左半段也是「有序」的。用 < 会漏掉。

这个判断是这题唯一的难点。想通了，整题就通了。

五、LC153 寻找旋转最小值 - 和右边比，不和左边比

同样是旋转数组，这回不找 target，找最小值。

最小值就在「旋转点」的位置 —— 升序被打断的地方。比如 [4,5,6,7,0,1,2]，旋转点在 7 和 0 之间，最小值是 0。

怎么找？拿 nums[mid] 和 nums[right] 比：

  • nums[mid] > nums[right]：mid 在旋转点左侧，最小值在右边，left = mid + 1
  • nums[mid] <= nums[right]：mid 在旋转点右侧（或就是旋转点本身），right = mid

为什么和 nums[right] 比而不是 nums[left]？

因为和 nums[left] 比有个致命问题：当数组完全有序没旋转时，nums[mid] > nums[left] 恒成立，你分不清「左半段有序」和「整个数组有序」。而和 nums[right] 比没有这个歧义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) { // 注意：< 不是 <=
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid; // mid 本身可能就是最小值
            }
        }
        return nums[left];
    }
}

避坑：

  • 循环条件 left < right，不是 <=。因为 right = mid 不是 mid - 1，用 <= 会死循环
  • right = mid 不是 mid - 1，因为 mid 可能就是答案，不能把它跳过去

这两点和 LC33 完全相反。LC33 是「找到了就排除」，这题是「找到了就留着」。搞混了就完蛋。

六、LC4 寻找两个正序数组的中位数 - 在两个数组上各切一刀

二分查找的最终 Boss。

两个有序数组，找中位数，要求 O(log(m+n))。

合并再找？O(m+n)，太慢了。

思路是这样的：中位数的本质是把所有元素分成两半，左半的最大值小于右半的最小值。那我在两个数组上各切一刀：

1
2
nums1:  [... 左半 | 右半 ...]
nums2:  [... 左半 | 右半 ...]

切完之后，如果满足 nums1 左半最大 <= nums2 右半最小 且 nums2 左半最大 <= nums1 右半最小，这条分割线就找对了。

对较短的数组做二分，枚举分割位置 i，由 j = (m+n+1)/2 - i 自动确定另一个数组的分割位置。为什么要在短数组上二分？因为如果 i 太大，j 会变成负数。短数组保证了 i 的范围足够小，j 始终合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 在短数组上二分，防止 j 越界
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length, n = nums2.length;
        int left = 0, right = m;

        while (left <= right) {
            int i = (left + right) / 2;       // nums1 分割位置
            int j = (m + n + 1) / 2 - i;      // nums2 分割位置

            // 边界处理：分割线贴边时用极值兜底
            int maxLeft1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            int minRight1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
            int maxLeft2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            int minRight2 = (j == n) ? Integer.MAX_VALUE : nums2[j];

            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                // 分割线找对了
                if ((m + n) % 2 == 0) {
                    return (Math.max(maxLeft1, maxLeft2) +
                            Math.min(minRight1, minRight2)) / 2.0;
                } else {
                    return Math.max(maxLeft1, maxLeft2);
                }
            } else if (maxLeft1 > minRight2) {
                right = i - 1; // nums1 切太靠右了
            } else {
                left = i + 1;  // nums1 切太靠左了
            }
        }
        throw new IllegalArgumentException();
    }
}

避坑：

  • 必须在较短数组上二分，否则 j 可能为负
  • 边界用 MIN_VALUE 和 MAX_VALUE 兜底，i=0 或 i=m 时数组的一侧是空的
  • j = (m+n+1)/2 里的 +1 是为了让奇数个时左半多一个元素，中位数直接取 max(左半最大) 就行

这题难的不是二分本身，而是把「中位数」这个概念转化成「分割线」的思路。想通了这个映射，代码反而比前面几道题还清晰。

碎碎念

二分查找的代码量都不大，每道题也就十几二十行。但魔鬼全在细节里 —— 循环条件是 < 还是 <=，right 是 mid 还是 mid - 1，和左边比还是和右边比。

这些细节不是靠背的。你得理解每一行代码背后的不变量是什么，循环退出的时候各个变量指向哪里。

这六道题串起来的线索就一条：在正确的位置切一刀。

LC35 在有序数组上切，LC74 把二维展平了切，LC34 用 lower_bound 切两次，LC33 和 LC153 在旋转数组上找对了方向再切，LC4 在两个数组上同时切。

切的依据不同，但刀法一样 —— 每次砍掉一半，O(log n) 收工。

下次面试遇到二分，别慌，先想清楚这一刀该切在哪。