LeetCode Hot 100 · 二分查找篇

二分查找是整个算法面试里「最不该丢分」的一类题：套路极其固定，但又是「最容易被边界条件打崩」的一类题。绝大多数人死循环、越界、少一个多一个下标，问题都出在开闭区间的选择和 mid 的取法上，而不是二分思想本身。

这一篇先帮你立住两套模板，再逐个拆 Hot 100 里的 6 道二分题。掌握这两套模板，这 6 题以及它们背后的延伸题（278、69、240、81、154……）都能一把梭。

模板一：闭区间 [l, r]（适合「精确查找」）

int l = 0, r = n - 1;
while (l <= r) {                       // 闭区间，l == r 时仍要检查
    int mid = l + ((r - l) >> 1);      // 防溢出写法
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) l = mid + 1;
    else                         r = mid - 1;
}
return -1;                             // 没找到

模板二：开区间 (l, r)（适合「找第一个满足条件的位置」）

int l = -1, r = n;                     // 开区间，两端都不考虑
while (l + 1 < r) {                    // 区间内至少还有一个元素时继续
    int mid = l + ((r - l) >> 1);
    if (满足条件(nums[mid])) r = mid;  // mid 可能是答案，右边界收缩到 mid
    else                    l = mid;   // mid 一定不是答案，左边界推进
}
return r;                              // r 就是第一个满足条件的位置

一句话记忆：找「精确值」用闭区间，找「第一个 ≥ x / 第一个满足某条件」用开区间。开区间天然规避了「插入位置在末尾」「第一个满足条件的位置不存在」等尴尬的越界处理。

下面逐题拆解。

#35 搜索插入位置

题意

给定一个升序数组 nums 和目标值 target，返回 target 的下标；如果不存在，返回它应当被按顺序插入的位置。

输入：nums = [1,3,5,6], target = 5   → 输出：2   （5 存在，返回下标）
输入：nums = [1,3,5,6], target = 2   → 输出：1   （2 不存在，应插在 3 之前）
输入：nums = [1,3,5,6], target = 7   → 输出：4   （比所有元素都大，插到末尾）

题目本质：本质是二分查找第一个 ≥ target 的位置——找到满足 nums[mid] >= target 的最左下标。这个下标同时就是「存在时的位置」和「不存在时的插入位置」，一举两得。

现实类比：字典插词。翻开一本排序好的字典，二分翻页，找到「第一个不比目标词小」的位置，那里就是这个词该插入的地方——目标词若已存在，那个位置正好就是它自己。

难点与易错点

1. 开区间的初始化：l = -1, r = n，两端都不考虑。这样当 target 比所有元素都大时，返回的 r = n 正好是合法的「插入到末尾」位置；如果用闭区间 l=0, r=n-1，插入末尾时就要额外特判，容易漏。
2. 循环条件与返回值：循环条件是 l + 1 < r（区间内至少还剩一个元素），结束时 l + 1 == r。返回的是 r，不是 l，也不是 mid——r 始终被维护为「第一个 ≥ target」的候选位置。
3. mid 的取法：mid = l + ((r - l) >> 1)，而不是 (l + r) / 2。后者在 l、r 都很大时可能 int 溢出（l + r 超过 2^31 - 1），这是面试官最爱挑的细节。
4. 比较用的是 >= 而不是 >：nums[mid] >= target 时 r = mid（mid 可能是答案，不能丢），nums[mid] < target 时 l = mid（mid 太小，一定不是答案）。一旦写成 >，相等的元素就会被错误地丢到左半，导致找不到。

解法一：暴力 / 直观

从头到尾扫描，找到第一个 >= target 的位置返回；扫完没找到就说明 target 比所有元素大，返回 n。

class Solution {
    public int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            // 找到第一个 >= target 的位置，就是要插入/命中的位置
            if (nums[i] >= target) {
                return i;
            }
        }
        // 所有元素都小于 target，插到末尾
        return nums.length;
    }
}

复杂度推导：最坏情况需要遍历整个数组 n 个元素，所以时间复杂度是 O(n)；只用了一个循环变量，空间复杂度 O(1)。

瓶颈：时间是线性的。当数组很大（比如 n = 10^7）时，一次查询要扫一千万次，而题目数组已经有序，这个有序信息被完全浪费了——这是可以优化的关键。

解法二：优化 / 最优

用开区间二分，每轮把搜索范围砍一半，直接定位第一个 ≥ target 的位置。

class Solution {
    public int searchInsert(int[] nums, int target) {
        // 开区间二分：l 始终 < 答案，r 始终 >= 答案
        int l = -1, r = nums.length;

        while (l + 1 < r) {                    // 区间内至少还剩一个元素
            int mid = l + ((r - l) >> 1);      // 防溢出的 mid

            if (nums[mid] >= target) {
                r = mid;   // mid 可能是答案，右边界收缩到 mid（不能是 mid-1）
            } else {
                l = mid;   // mid 太小，左边界推进
            }
        }

        return r; // r 就是第一个 >= target 的位置（即插入位置）
    }
}

复杂度逐步推导：

• 初始时，区间 [l, r] 覆盖了 n + 1 个候选位置（从下标 -1 到 n）。
• 第 1 轮循环后，区间长度变成 (n+1)/2；第 2 轮后变成 (n+1)/4；……第 k 轮后变成 (n+1)/2^k。
• 循环在区间只剩「一个元素」（即 l + 1 == r）时结束，此时 (n+1)/2^k ≈ 1，解得 2^k ≈ n+1，即 k = log2(n+1)。
• 所以循环执行次数是 O(log n)，每轮只做常数次比较，时间复杂度 O(log n)。
• 全程只用了 l、r、mid 三个变量，空间复杂度 O(1)。

多解法对比

本题约束下数组是升序的，且可能很大，二分每轮砍半带来的 O(log n) 是质变（n=10^6 时线性要 100 万次，二分只要约 20 次），因此选二分。

CodeTop 变体

• 同套路延伸：278. 第一个错误的版本（本质是「找第一个 isBadVersion(mid) 为真的位置」，与「第一个 ≥ target」是同构题，把判断条件从 >= target 换成 isBadVersion(mid) 即可）；69. x 的平方根（找最大的满足 mid*mid <= x 的整数，是「找最后一个满足条件」的变体）。
• 字节/美团高频追问：把本题的 target 换成「找第一个严格大于 x 的位置」（> 而非 >=，返回值语义从「插入位置」变成「下一个更大的元素」），并要求数组允许重复元素时返回最左/最右位置——这正是下一题 #34 要解决的场景。

#74 搜索二维矩阵

题意

给定一个 m x n 矩阵：每行内部升序，且每行第一个元素大于上一行最后一个元素。判断 target 是否在矩阵中。

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

题目本质：因为「每行第一个元素大于上一行末尾」，把整个矩阵按行展开就是一条严格递增的一维数组。本质是把二维坐标映射成一维下标后，直接套标准二分——matrix[mid/n][mid%n] 把一维 mid 换算回二维坐标。

现实类比：把排好序的表格展平成一行。就像把一张按字典序排好的表格铺平成一长条，用二分在长条上找，找到后再用「除法和取余」把位置换算回原来的行、列。

难点与易错点

1. 坐标映射：一维下标 mid 对应的行列是 row = mid / n、col = mid % n，其中 n 是列数（matrix[0].length），不是行数。写错 n 的含义，映射就全错。
2. 总长度是 m * n：二分右边界是 r = m * n - 1，不是 m - 1 也不是 n - 1，这是最常见的越界/漏检来源。
3. 空矩阵防御：本题约束 m >= 1, n >= 1，但面试官可能追问 matrix 或 matrix[0] 为空的情况，应提前判断返回 false。
4. 本质前提：这里能「一次二分」的前提是矩阵整体有序（强条件）。如果只是「每行每列各自升序」而整体不保证有序（如 #240），一次二分就不成立，得换「从右上角/左下角」的走法——这恰恰是常见的变体追问。

解法一：暴力 / 直观

双重循环遍历整个矩阵，逐元素比较。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }
}

复杂度推导：两重循环，外层 m 次、内层 n 次，总共 m * n 次比较，时间复杂度 O(m×n)；只用循环变量，空间复杂度 O(1)。

瓶颈：完全没用到「整体有序」这个强条件。当矩阵很大（10^3 × 10^3）时，要比较 100 万次，而有序条件下二分只需约 20 次。

解法二：优化 / 最优

把矩阵当成一条长度为 m * n 的一维有序数组，闭区间二分。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int l = 0, r = m * n - 1;              // 一维数组的闭区间 [0, m*n-1]

        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            int val = matrix[mid / n][mid % n]; // 一维坐标 → 二维坐标

            if      (val == target) return true;
            else if (val >  target) r = mid - 1;
            else                    l = mid + 1;
        }

        return false;
    }
}

复杂度逐步推导：

• 设一维总元素数 N = m * n。初始搜索区间长度为 N。
• 每轮循环区间减半：第 1 轮后为 N/2，第 k 轮后为 N/2^k。
• 循环在区间为空（l > r）时结束，此时 N/2^k ≈ 1，即 k = log2(N)。
• 因此循环执行 O(log N) = O(log(m×n)) 次，每轮做一次坐标换算和一次比较，时间复杂度 O(log(m×n))。
• 只用了常数个变量，空间复杂度 O(1)。

💭 思考：看到「每行第一个元素大于上一行末尾」为什么要联想到「展平成一条一维数组」？——因为这是判断「能否一次二分」的信号：只要整个矩阵能排成一条严格递增序列，二分就适用。暴力双层遍历 O(m×n) 把「整体有序」这个强条件完全浪费了；把一维 mid 用 (mid/n, mid%n) 映射回二维坐标，就把它变成标准闭区间二分，复杂度从 O(m×n) 塌缩到 O(log(m×n))。反向验证一下：如果只有「每行每列各自升序」而没有整体有序（如 #240），这条展平的序列就不存在，这招也就失效——信号和前提是一体的。

多解法对比

本题矩阵满足「整体有序」的强约束，一维映射二分把 m×n 降到 log(m×n)，是质变，因此选它。

CodeTop 变体

• 真实高频追问（字节/腾讯常考）：240. 搜索二维矩阵 II——只保证「每行升序、每列升序」，不保证整体有序。此时一次二分失效，正确做法是从右上角（或左下角）出发，val > target 则左移一列、val < target 则下移一行，复杂度 O(m+n)。面试官通常拿这题检验你是否真的理解「整体有序」这个前提，而不是背模板。
• 同套路延伸：给一个有序二维矩阵求「第 k 小元素」的思路铺垫（可用值域二分 + 计数，Hard 题 378 的思路雏形）。

#34 在排序数组中查找元素的第一个和最后一个位置

题意

给定升序数组 nums 和目标值 target，返回 target 的起始和结束下标；如果 target 不存在，返回 [-1, -1]。要求 O(log n)。

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

题目本质：本质是两次二分。一次找「第一个 ≥ target 的位置」（left），一次找「第一个 > target 的位置减一」（right），也就是「≤ target 的最后一个位置」。两个边界都可以复用同一个 lowerBound 函数。

现实类比：找书架上某本书的第一本和最后一本。书架上同一种书连续排成一摞，第一次二分找到这摞书的左端，第二次二分找到右端，首尾下标就齐了。

难点与易错点

1. 复用 lowerBound 求右边界：右边界 = 「第一个 > target 的位置」- 1 = lowerBound(nums, target + 1) - 1。这里的 target + 1 是关键技巧——把「找最后一个等于 target」转化成「找第一个大于 target 再回退一位」，省去写第二个反向二分。
2. target + 1 可能溢出：当 target = Integer.MAX_VALUE 时 target + 1 溢出为负数，导致错误。面试可提一句：在本题数据范围（元素为 int）内 target 通常是 nums 中存在的普通值，一般安全；但严谨写法可用 lowerBound(nums, target + 1L) 或改传 long，展示你对边界的敏感。
3. 越界与不存在的判断：拿到 left 后必须先判断 left == nums.length || nums[left] != target，两种情况都说明 target 不存在（前者 target 比所有元素大，后者 target 不在数组中），返回 [-1,-1]。先判再算 right，顺序不能反。
4. 开区间二分返回 r：lowerBound 返回的是「第一个 ≥ target」的下标，可能等于 nums.length（target 比所有元素大），这是合法返回值，调用方要能接住这个「越界」语义。

解法一：暴力 / 直观

两次线性扫描：一次从头找第一个等于 target 的位置，一次从尾找最后一个等于 target 的位置。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = -1, right = -1;

        // 从前向后找第一个 target
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) { left = i; break; }
        }
        // 从后向前找最后一个 target
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] == target) { right = i; break; }
        }

        return new int[]{left, right};
    }
}

复杂度推导：两次线性扫描，各最多遍历 n 个元素，时间复杂度 O(n)；只用常数个变量，空间复杂度 O(1)。

瓶颈：当 n 很大（如 10^7）时两次扫描代价高；且题目明确要求 O(log n)，线性解法不达标。有序数组的「首尾位置」天然可以用二分定位。

解法二：优化 / 最优

复用 lowerBound 做两次二分。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = lowerBound(nums, target);

        // 若左边界越界或目标值不存在
        if (left == nums.length || nums[left] != target) {
            return new int[]{-1, -1};
        }

        // 右边界 = 第一个 > target 的位置 - 1（即 <= target 的最后一个位置）
        int right = lowerBound(nums, target + 1) - 1;

        return new int[]{left, right};
    }

    // 返回第一个 >= target 的下标（lower_bound）
    private int lowerBound(int[] nums, int target) {
        int l = -1, r = nums.length;          // 开区间二分
        while (l + 1 < r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] >= target) r = mid; // mid 可能是答案，收缩到 mid
            else                     l = mid;
        }
        return r; // 第一个 >= target 的位置
    }
}

复杂度逐步推导：

• 主函数调用了两次 lowerBound，每次 lowerBound 内部是标准二分：初始区间长度 n+1，每轮减半，第 k 轮后为 (n+1)/2^k，循环结束于 (n+1)/2^k ≈ 1，即 k = O(log n)。
• 两次二分相加：O(log n) + O(log n) = O(2 log n) = O(log n)。
• 所以时间复杂度 O(log n)；除返回值外只用了常数个变量，空间复杂度 O(1)。

多解法对比

本题题目本身要求 O(log n)，且「复用 lowerBound」把左右边界统一到一个函数，代码更短、更不易错，是唯一达标且优雅的解法。

CodeTop 变体

• 真实高频追问：给定 target 的出现次数。答案是 right - left + 1（两个边界求出来后直接相减），这也是很多公司（字节、阿里）在原题上的直接追问。
• 同套路延伸：278. 第一个错误的版本（找第一个满足条件的下标，复用 lowerBound 思想）；面试追问：若数组不是升序而是先增后减（单峰），如何找峰值——引出 162. 寻找峰值。

#33 搜索旋转排序数组

题意

一个升序数组在某个未知下标处被旋转（例如 [0,1,2,4,5,6,7] 在 3 处旋转成 [4,5,6,7,0,1,2]），给定 target，返回其下标；不存在返回 -1。要求 O(log n)，数组无重复元素。

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

题目本质：旋转数组二分后至少有一半是有序的。本质是二分 + 判断有序半段：先判断左半还是右半有序，再看 target 是否落在那个有序半段内，从而决定缩到哪一半继续二分。

现实类比：旋转书架找书。书架被从某处切断后首尾重接，次序乱了，但每次都能保证左半或右半是完整有序的。于是每次都先看「哪半边还是整齐的」，再判断要找的书在不在这整齐的半边里，在就去这半边，不在就去另一半。

难点与易错点

1. 判断哪半有序：用 nums[l] <= nums[mid] 判断「左半 [l, mid] 有序」，否则「右半 [mid, r] 有序」。必须用 <= 而不是 <——当只剩两个元素（l 和 mid 指向同一元素）时，左半应视为有序，用 < 会误判，导致死循环或漏判。
2. 有序半段内的区间判断用严格不等号：nums[l] <= target && target < nums[mid] 这里 target < nums[mid] 是严格小于，因为 target == nums[mid] 的情况已在循环开头提前返回；另一侧对称地写 nums[mid] < target && target <= nums[r]。
3. target 不在有序半段时的收缩方向：很多人算反。左半有序但 target 不在 [nums[l], nums[mid]) 内，说明 target 在右半，应 l = mid + 1；反之右半有序但 target 不在 (nums[mid], nums[r]] 内，说明在左半，应 r = mid - 1。
4. 闭区间配套：这里用闭区间 while (l <= r)，mid 取 l + ((r - l) >> 1) 防溢出；与 #153 的「只和 nums[r] 比」不同，本题要同时用到 nums[l]、nums[mid]、nums[r] 定位 target。

解法一：暴力 / 直观

线性扫描，逐元素找 target。

class Solution {
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

复杂度推导：最坏遍历 n 个元素，时间复杂度 O(n)；空间复杂度 O(1)。

瓶颈：无视「旋转后仍有一半有序」的结构信息。题目要求 O(log n)，线性不达标。数组虽然被旋转，但仍保留着足够的「局部有序」可供二分利用。

解法二：优化 / 最优

二分 + 每次锁定有序半段，判断 target 归属。

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

        while (l <= r) {
            int mid = l + ((r - l) >> 1);

            if (nums[mid] == target) return mid;

            if (nums[l] <= nums[mid]) {
                // 左半段 [l, mid] 有序
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1; // target 落在左半有序段
                } else {
                    l = mid + 1; // target 在右半（无序的那半）
                }
            } else {
                // 右半段 [mid, r] 有序
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1; // target 落在右半有序段
                } else {
                    r = mid - 1; // target 在左半（无序的那半）
                }
            }
        }

        return -1;
    }
}

复杂度逐步推导：

• 初始区间长度为 n。虽然数组被旋转，但每轮循环一定能把区间长度砍半——因为我们每次都能明确确定 target 必然落在左半或右半之一，排除掉另一半。
• 第 1 轮后区间长度为 n/2，第 k 轮后为 n/2^k。
• 循环在区间为空（l > r）时结束，n/2^k ≈ 1，得 k = O(log n)。
• 因此时间复杂度 O(log n)；只用常数个变量，空间复杂度 O(1)。

💭 思考：旋转数组为什么能「二分」，抓住的到底是什么？——二分成立的前提是「每轮能确定目标在哪一半」。旋转数组整体乱序，但取 mid 后，nums[l] <= nums[mid] 就能判定左半 [l, mid] 有序（否则右半有序）；而在有序半段里 target 是否落在区间内是可判的，于是每轮仍能确定性地排除一半，O(log n) 才保得住。看到「旋转数组 + 要求 O(log n)」这个组合，就该想到「局部有序 + 锁定有序半段」，而不是先还原整个数组再二分——那会丢掉旋转结构里仅存的有序信息。

多解法对比

本题要求 O(log n) 且数组无重复，二分每次确定性砍半，是唯一达标解法。

CodeTop 变体

• 真实高频追问（字节/美团/微软都爱问）：81. 搜索旋转排序数组 II——数组允许重复元素。重复会让「判断哪半有序」失效（如 [1,0,1,1,1]，nums[l] == nums[mid] == nums[r] 时无法判断哪半有序），只能 l++ / r-- 跳过重复，最坏退化到 O(n)，均摊仍是 O(log n)。
• 同套路延伸：下一题 #153「找旋转数组最小值」、#154「找最小值（含重复）」是同一家族，掌握「旋转后至少一半有序」这个核心即可串联。

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

题意

给定旋转后的升序数组（无重复元素），返回其中的最小值。假设旋转次数 k 可为 0（即未旋转）。

输入：nums = [3,4,5,1,2]
输出：1
输入：nums = [4,5,6,7,0,1,2]
输出：0

题目本质：最小值就是「右半段的第一个元素」，即二分找断点——找第一个满足 nums[mid] < nums[r] 的位置。关键技巧：以 nums[r] 为基准，而不是 nums[l]。

现实类比：找一排票据的日期断点。一沓按日期排列的票据在某处被旋转，日期从「大」突然变「小」的那一处就是断点，用二分快速定位这个「由大变小的拐点」。

难点与易错点

1. 基准选 nums[r]，不是 nums[l]：这是本题最核心、最容易错的一点。若拿 nums[mid] 和 nums[l] 比，在「未旋转（完全有序）」的数组上会出错（此时 nums[mid] 始终 > nums[l]，会误以为断点在右边，把最小值丢掉）。拿 nums[r] 比则天然正确：最小值一定 ≤ nums[r]。
2. r = mid 而不是 r = mid - 1：当 nums[mid] < nums[r] 时，mid 本身可能是最小值，不能排除它，所以右边界收缩到 mid（不是 mid-1）；而当 nums[mid] > nums[r] 时，mid 一定比右端大、不可能是最小值，才 l = mid + 1。
3. 循环条件 l < r，返回 nums[l]：这里不是闭区间 l <= r，因为 r 可能保留着候选最小值，最后 l == r 时即为答案位置。写成 l <= r 会死循环。
4. 未旋转（k=0）也要正确处理：此时数组完全升序，nums[mid] 始终 < nums[r]，r 不断左移收缩，最终 l == r == 0，返回 nums[0]，天然正确，无需特判。

解法一：暴力 / 直观

遍历找最小值。

class Solution {
    public int findMin(int[] nums) {
        int min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < min) {
                min = nums[i];
            }
        }
        return min;
    }
}

复杂度推导：遍历 n 个元素，时间复杂度 O(n)；空间复杂度 O(1)。

瓶颈：旋转数组「两段各有序、断点唯一」的结构没被利用。题目要求 O(log n)，线性不达标。

解法二：优化 / 最优

以 nums[r] 为基准的二分找断点。

class Solution {
    public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1;

        while (l < r) {
            int mid = l + ((r - l) >> 1);

            // nums[mid] > nums[r]：最小值在 [mid+1, r]
            // nums[mid] < nums[r]：最小值在 [l, mid]（mid 可能是最小值）
            if (nums[mid] > nums[r]) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }

        return nums[l]; // l == r，即最小值位置
    }
}

复杂度逐步推导：

• 初始区间长度 n。每轮循环，无论走 l = mid + 1 还是 r = mid，区间长度都会严格减半（两种分支都把候选区间缩到原来的一半）。
• 第 1 轮后区间长度为 n/2，第 k 轮后为 n/2^k。
• 循环在 l == r（区间只剩一个元素）时结束，n/2^k ≈ 1，得 k = O(log n)。
• 因此时间复杂度 O(log n)；只用常数个变量，空间复杂度 O(1)。

💭 思考：为什么找最小值要拿 nums[r] 当基准，而不是 nums[l]？——最小值就是「断点右边的第一个元素」。若拿 nums[l] 比，未旋转（完全升序）时 nums[mid] 恒大于 nums[l]，会误以为断点在右边、把最小值丢掉；拿 nums[r] 比则天然正确，因为最小值一定 ≤ nums[r]。这就是「看到『旋转 + 找最小值』，先想清楚基准选谁」的原因——基准选错，二分的收缩方向就全错，复杂度分析再漂亮也白搭。

多解法对比

本题要求 O(log n)，二分是唯一达标解法；「以 nums[r] 为基准」是能覆盖「未旋转」边界的正确写法。

CodeTop 变体

• 真实高频追问（字节/微软常考）：154. 寻找旋转排序数组中的最小值 II——数组允许重复元素。当 nums[mid] == nums[r] 时无法判断断点在哪半，只能 r-- 保守收缩，最坏退化到 O(n)（如全相等数组）。
• 同套路延伸：结合 #33，先二分找最小值（断点）再二分搜 target 是另一种解 #33 的思路；本家族还可延伸到「旋转数组找峰值」类问题。

#4 寻找两个正序数组的中位数

题意

给定两个升序数组 nums1 和 nums2，返回两数组合并后的中位数，要求 O(log(m+n)) 时间复杂度。

输入：nums1 = [1,3], nums2 = [2]
输出：2.0            （合并 [1,2,3]，中位数 2）
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.5            （合并 [1,2,3,4]，中位数 (2+3)/2 = 2.5）

题目本质：本质是二分划分（Partition）。在较短数组中二分切割点 i，在较长数组中对应切 j = (m+n+1)/2 - i，保证左右两部分元素个数相等（奇数时左多一个），并通过比较 A[i-1] vs B[j] 和 B[j-1] vs A[i] 调整切割点，使左半最大 ≤ 右半最小，中位数即落在分割线两侧。

现实类比：两队按身高排好的学生合并后找中间那个。不用真正合并成一支大队，而是用二分反复调整一条「分割线」，让左边总人数正好是一半，且左边最高的比右边最矮的还矮——此时分割线两边的数就是中位数。

难点与易错点

1. 在较短数组上二分：先保证 A 是较短数组（m <= n），二分 i ∈ [0, m]。这样 j = half - i 一定落在 [0, n] 内，不会越界；同时把复杂度压到 O(log(min(m,n)))。若在长数组上二分，j 可能算出负数导致越界。
2. half = (m + n + 1) / 2 的向上取整：保证总数为奇数时左半比右半多一个，这样奇数时中位数直接是 maxLeft；偶数时左半元素数 = (m+n)/2，正好一半。
3. 边界用极值：切割线可能落在数组最左（i == 0）或最右（i == m），此时 A[i-1] 或 A[i] 会越界。用 Integer.MIN_VALUE 表示「左边界外的最小值」、Integer.MAX_VALUE 表示「右边界外的最大值」，统一比较逻辑，避免一堆 if 特判。
4. 调整方向别写反：aLeft > bRight 说明 A 分给左半的太多了（i 太大），要 hi = i - 1 左移；bLeft > aRight 说明 A 分给左半的太少（i 太小），要 lo = i + 1 右移。两者方向相反，是最容易写反的一行。
5. 偶数的平均值用 2.0：return (maxLeft + minRight) / 2.0 必须用浮点除法，写成 / 2 会整数截断，丢掉 .5 的小数部分。

解法一：暴力 / 直观

归并两个有序数组（合并成一个有序数组），再直接取中位数。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] merged = new int[m + n];

        // 双指针归并两个有序数组
        int i = 0, j = 0, k = 0;
        while (i < m && j < n) {
            merged[k++] = nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++];
        }
        while (i < m) merged[k++] = nums1[i++];
        while (j < n) merged[k++] = nums2[j++];

        int total = m + n;
        if (total % 2 == 1) {
            return merged[total / 2];                    // 奇数：中间一个
        } else {
            return (merged[total / 2 - 1] + merged[total / 2]) / 2.0; // 偶数：中间两个平均
        }
    }
}

复杂度推导：归并需要遍历两个数组的全部 m + n 个元素，时间复杂度 O(m+n)；额外开辟了长度 m+n 的合并数组，空间复杂度 O(m+n)。

空间优化：其实只需要归并到「中位数位置」就停，不需要整个数组，可把空间降到 O(1)。但时间复杂度仍是 O(m+n)。

瓶颈：时间 O(m+n) 不满足题目 O(log(m+n)) 的要求；空间 O(m+n) 对大数据也是负担。合并本身就是把「找中位数」做成了「完整排序」，是冗余的。

解法二：优化 / 最优

在较短数组上二分切割点，无需真正合并。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 保证在较短的数组中二分（减少二分区间）
        int[] A = nums1.length <= nums2.length ? nums1 : nums2;
        int[] B = nums1.length <= nums2.length ? nums2 : nums1;
        int m = A.length, n = B.length;
        int half = (m + n + 1) / 2; // 左半总元素数（向上取整处理奇偶）

        int lo = 0, hi = m;

        while (lo <= hi) {
            int i = lo + ((hi - lo) >> 1); // A 中取 i 个元素进左半
            int j = half - i;               // B 中取 j 个元素进左半

            // 边界用极值处理分割线在数组边缘的情况
            int aLeft  = i == 0 ? Integer.MIN_VALUE : A[i - 1];
            int aRight = i == m ? Integer.MAX_VALUE : A[i];
            int bLeft  = j == 0 ? Integer.MIN_VALUE : B[j - 1];
            int bRight = j == n ? Integer.MAX_VALUE : B[j];

            if (aLeft > bRight) {
                hi = i - 1; // A 给左半太多，i 太大，左移
            } else if (bLeft > aRight) {
                lo = i + 1; // A 给左半太少，i 太小，右移
            } else {
                // 正确的切割：左半最大 <= 右半最小
                int maxLeft  = Math.max(aLeft,  bLeft);
                int minRight = Math.min(aRight, bRight);

                if ((m + n) % 2 == 1) return maxLeft;          // 奇数：返回左半最大
                return (maxLeft + minRight) / 2.0;              // 偶数：返回中间两数平均
            }
        }

        return 0.0; // 不会到达（正确切割一定存在）
    }
}

复杂度逐步推导：

• 二分的区间是 i ∈ [0, m]，长度为 m + 1，其中 m = min(原 m, 原 n)（我们在较短数组 A 上二分）。
• 每轮循环，根据 aLeft > bRight 或 bLeft > aRight 把区间砍半：第 1 轮后为 (m+1)/2，第 k 轮后为 (m+1)/2^k。
• 循环在区间为空（lo > hi）或找到正确切割时结束，最多执行 k = O(log m) 次。
• 因为 m = min(m, n)，所以时间复杂度 O(log m) = O(log(min(m,n)))。
• 每轮只做常数次比较和取极值，除原数组外只用了常数个变量，空间复杂度 O(1)。

为什么不是 O(log(m+n))？因为二分只发生在较短的 A 上，区间规模是 min(m, n) 而非 m+n，所以是 O(log(min(m,n)))——它比题目要求的 O(log(m+n)) 更紧，自然满足要求。

💭 思考：为什么这题不能用「归并两个数组」而必须「二分划分」？——看到「两个有序数组 + 要求 O(log(m+n))」这个信号，就知道线性归并 O(m+n) 直接不达标。中位数本质上只关心「左半最大 ≤ 右半最小」这一条分界线，并不需要真的排好整个合并序列。于是把问题降维成：在较短数组上二分切割点 i，另一个切割点 j = half - i 由它唯一确定，再用 A[i-1] vs B[j]、B[j-1] vs A[i] 判断分界线摆对没有、该往左还是往右调。这就是「从完整归并 → 只维护一条分割线」的思路，复杂度也从 O(m+n) 压到 O(log(min(m,n)))。

多解法对比

本题是 Hard，硬性要求 O(log(m+n))，归并的线性时间直接不达标；二分划分在短数组上二分，复杂度甚至优于题目下界要求，且零额外空间，是唯一正确打开方式。

CodeTop 变体

• 真实高频追问（字节/腾讯/微软都爱考的 Hard）：把「中位数」泛化为**「两个有序数组的第 k 小元素」**。中位数只是 k = (m+n+1)/2（奇数）或 (m+n)/2 与 (m+n)/2+1（偶数）的特例。面试官常让你先写「第 k 小」再套中位数，或反过来。
• 同套路延伸：合并 K 个有序数组的中位数 / 第 k 小（可两两归并、或用「值域二分 + 计数」的思路，Hard 题 4 号思路的推广）；以及用「二分答案 + 计数」求第 k 小的通用范式（如 378. 有序矩阵中第 K 小的元素）。

总结：六题的二分「四件套」

一句话收束：二分难不在「折半」，而在「边界」——想清楚开闭区间、mid 取法、基准选谁、返回什么，这 6 题及其延伸题便一通百通。

章末提问

1. 二分到底用闭区间 l <= r 还是开区间 l + 1 < r？怎么选？——结论：找「精确值」用闭区间，找「第一个满足条件的位置」用开区间。因为开区间的 r 天然维护「可能的答案」，能统一处理「插到末尾」「答案不存在」这些越界场景，不用额外特判。
2. #153 找最小值为什么要以 nums[r] 为基准，而不是 nums[l]？——结论：因为最小值一定 ≤ nums[r]，拿 nums[r] 比天然正确；若拿 nums[l] 比，在「未旋转（完全有序）」的输入上会误判断点在右边，把最小值丢掉。
3. #4 中位数为什么要在「较短的数组」上二分，在长数组上二分会怎样？——结论：因为切割点 j = half - i 由 i 唯一确定，只有 i 在短数组上二分，j 才一定落在长数组合法区间内、不会越界，且复杂度压到 O(log(min(m,n)))。在长数组上二分，j 可能算出负数或越界。