06 二分查找的变体：旋转有序数组与有序矩阵

二分查找的变体：旋转有序数组与有序矩阵

摘要

上一篇建立了二分查找的标准模板框架。本篇进入”有序性被部分破坏”的场景：旋转有序数组和有序矩阵。这两道题是二分查找中最有代表性的”变形题”，考察的核心是：当有序性不完整时，如何找到仍然可以做二分判断的局部有序区间。掌握这两道题，就掌握了处理一大类”有序性被干扰”问题的思维框架。

---

第 1 章 旋转有序数组：局部有序的利用

1.1 旋转的本质

一个原本升序排列的数组 [0, 1, 2, 4, 5, 6, 7] 在某个位置 $k$ 处”旋转”，得到 [4, 5, 6, 7, 0, 1, 2]（在下标 4 处旋转）。

旋转后，数组的全局有序性被破坏了，但局部有序性仍然存在：数组被切成了两段，每段内部仍然是升序的。

旋转前: [0, 1, 2, 4, 5, 6, 7]
旋转后: [4, 5, 6, 7 | 0, 1, 2]
             左半段 |  右半段

关键结论：无论 mid 落在哪里，mid 左边或右边必有一半是连续有序的。

具体来说，对于任意 mid：

• 如果 nums[left] <= nums[mid]：左半段 [left, mid] 是连续有序的
• 如果 nums[left] > nums[mid]：右半段 [mid, right] 是连续有序的

这是旋转数组二分查找的突破口：每次找到那个连续有序的半段，然后判断 target 是否在其中，从而决定往哪边继续搜索。

1.2 LeetCode 33：搜索旋转排序数组（无重复元素）

题目：

LeetCode 33 - Search in Rotated Sorted Array（中等）

整数数组 nums 按升序排列，数组中的值互不相同。在某个下标 k 处旋转后，给你旋转后的数组 nums 和一个整数 target，如果 nums 中存在 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

输入: nums = [1], target = 0
输出: -1

算法设计：

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]) {
            // 左半段 [left, mid] 有序
            if (nums[left] <= target && target < nums[mid]) {
                // target 在有序的左半段内
                right = mid - 1;
            } else {
                // target 不在左半段，去右半段找
                left = mid + 1;
            }
        } else {
            // 右半段 [mid, right] 有序
            if (nums[mid] < target && target <= nums[right]) {
                // target 在有序的右半段内
                left = mid + 1;
            } else {
                // target 不在右半段，去左半段找
                right = mid - 1;
            }
        }
    }
 
    return -1;
}

1.3 逐步走通示例

以 nums = [4, 5, 6, 7, 0, 1, 2]，target = 0：

第一次循环：left=0, right=6

• mid = 3，nums[3] = 7，不等于 0
• nums[left]=4 <= nums[mid]=7：左半段 [0,3] 有序（值是 4,5,6,7）
• 判断 target=0 是否在 [4, 7) 中？不在
• left = mid + 1 = 4

第二次循环：left=4, right=6

• mid = 5，nums[5] = 1，不等于 0
• nums[left]=0 <= nums[mid]=1：左半段 [4,5] 有序（值是 0,1）
• 判断 target=0 是否在 [0, 1) 中？是（0 <= 0 < 1）
• right = mid - 1 = 4

第三次循环：left=4, right=4

• mid = 4，nums[4] = 0，等于 target！
• 返回 4 ✅

1.4 LeetCode 81：搜索旋转排序数组 II（含重复元素）

题目：

LeetCode 81 - Search in Rotated Sorted Array II（中等）

与 LeetCode 33 相同，但数组中可能含有重复元素。

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true

输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false

重复元素带来的难题：

当 nums[left] == nums[mid] 时，我们无法判断左半段是否有序。

例如：[1, 3, 1, 1, 1]，left=0, mid=2，nums[left]=1, nums[mid]=1。此时：

• 左半段 [1, 3, 1] 不是有序的（3 > 1）
• 但右半段 [1, 1, 1] 是”有序的”（虽然全相同）

我们无法区分这种情况，也就无法确定 target 在哪一侧。

解决方案：当 nums[left] == nums[mid] 时，无法做二分判断，只能让 left++，缩小问题规模，然后继续尝试。这使得最坏情况下（所有元素相同）退化为 $O(n)$，但平均情况仍然是 $O(\log n)$。

public boolean 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 true;
 
        // 关键区别：处理 nums[left] == nums[mid] 的情况
        if (nums[left] == nums[mid]) {
            left++;  // 无法判断，缩小问题规模
            continue;
        }
 
        if (nums[left] < nums[mid]) {
            // 左半段有序
            if (nums[left] <= target && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else {
            // 右半段有序
            if (nums[mid] < target && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
 
    return false;
}

生产避坑：LeetCode 33 vs 81 的核心区别

LeetCode 33（无重复）：nums[left] <= nums[mid] 可以判断左半段有序，< 符号足以区分情况。 LeetCode 81（有重复）：nums[left] == nums[mid] 时无法判断，必须特殊处理（left++）。 面试中被问到 33 后，很可能追问”如果有重复怎么办”，就是 81 的变体。

---

第 2 章 有序矩阵查找：降维二分与 Z 字形搜索

2.1 LeetCode 74：搜索二维矩阵（强有序矩阵）

题目：

LeetCode 74 - Search a 2D Matrix（中等）

给你一个满足下述两条属性的 $m\times n$ 整数矩阵：

• 每行中的整数从左到右按非递减顺序排列
• 每行的第一个整数大于前一行的最后一个整数

给你一个整数 target，如果 target 在矩阵中，返回 true；否则，返回 false。

输入: 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

关键特征：这个矩阵有一个特殊性质——每行末尾元素小于下一行首元素。这意味着如果把矩阵的所有行首尾相连，可以得到一个严格有序的一维序列！

[[1,  3,  5,  7 ],         展开为一维：
 [10, 11, 16, 20],  →→→   [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
 [23, 30, 34, 60]]

2.2 坐标映射：一维下标与二维坐标的转换

核心思路：把这个 $m\times n$ 的矩阵看作一个长度为 $m\times n$ 的有序数组，对一维下标做二分查找，然后把一维下标映射回二维坐标。

映射公式（设矩阵有 $n$ 列）：

• 一维下标 $i$ 对应二维坐标 $(\lfloor i/n\rfloor ,i\mathrm{mod}n)$
• 二维坐标 $(r,c)$ 对应一维下标 $r\times n+c$

public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    int left = 0, right = m * n - 1;
 
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int midVal = matrix[mid / n][mid % n];  // 一维下标映射到二维
 
        if (midVal == target) return true;
        else if (midVal < target) left = mid + 1;
        else right = mid - 1;
    }
 
    return false;
}

时间 $O(\log (mn))$，空间 $O(1)$。

这道题的难点不在二分本身，而在于发现”可以把矩阵展开为一维有序数组”这个关键洞察。面试中能快速说出”这个矩阵满足全局有序，可以做一次二分”，就已经展现出很强的分析能力。

2.3 LeetCode 240：搜索二维矩阵 II（弱有序矩阵）

题目：

LeetCode 240 - Search a 2D Matrix II（中等）

与 LeetCode 74 不同，这道题的矩阵每行从左到右递增、每列从上到下递增，但相邻行之间没有约束（每行末尾元素可能小于下一行首元素，也可能大于）。

输入: matrix = [[1,4,7,11,15],
               [2,5,8,12,19],
               [3,6,9,16,22],
               [10,13,14,17,24],
               [18,21,23,26,30]], target = 5
输出: true

输入: 上面的矩阵, target = 20
输出: false

为什么 LeetCode 74 的方法不适用？

因为这里矩阵不能展开为全局有序的一维序列。例如上面的矩阵，第一行末尾是 15，第二行首是 2，2 < 15，无法直接合并。

朴素思路一：每行做一次二分

对每一行单独做二分查找。时间 $O(m\log n)$，不够优。

朴素思路二：暴力遍历

$O(mn)$，太慢。

2.4 Z 字形搜索：从右上角出发

核心思路：从矩阵的右上角出发（坐标 (0, n-1)），利用矩阵的行列有序性，每次排除一行或一列：

• 当前元素 matrix[r][c] 等于 target：找到，返回 true
• 当前元素 大于 target：当前列的所有值都 >= matrix[r][c] > target（列有序），整列可以排除，c--
• 当前元素 小于 target：当前行的所有值都 <= matrix[r][c] < target（行有序），整行可以排除，r++

public boolean searchMatrix(int[][] matrix, int target) {
    int r = 0, c = matrix[0].length - 1;  // 从右上角开始
 
    while (r < matrix.length && c >= 0) {
        if (matrix[r][c] == target) return true;
        else if (matrix[r][c] > target) c--;  // 排除当前列
        else r++;                              // 排除当前行
    }
 
    return false;
}

为什么从右上角？

右上角的元素有一个独特性质：

• 它是该行的最大值（行从左到右递增，右上角在最右端）
• 它是该列的最小值（列从上到下递增，右上角在最顶端）

这两个性质让每次比较都能做出确定性的”排除”决策：

• 比 target 大 → 这个值太大了，且它是该列的最小值，所以整列都比 target 大（或者等于 target，但不等于，所以整列都更大），排除整列
• 比 target 小 → 这个值太小了，且它是该行的最大值，所以整行都比 target 小，排除整行

时间 $O(m+n)$（每次操作排除一行或一列，最多 $m+n$ 步），空间 $O(1)$。

设计哲学：为什么不从左上角或中心开始？

• 从左上角开始：matrix[0][0] 是行最小值也是列最小值。如果比 target 小，无法确定往右走还是往下走（两个方向的值都可能更大），无法做确定性排除。
• 从中心开始：无法做确定性排除，会有两个方向都可能包含 target 的情况。
• 从右上角或左下角：都具有”一个方向最大，另一个方向最小”的性质，每次可以确定性地排除一行或一列。两者等价，任选其一。

2.5 两道矩阵题的对比

维度	LeetCode 74（强有序）	LeetCode 240（弱有序）
约束	每行末 < 下行首	仅行、列内部有序
核心思路	展开为一维，做二分	Z 字形搜索（右上角/左下角）
时间复杂度	$O(\log (mn))$	$O(m+n)$
空间复杂度	$O(1)$	$O(1)$

$O(\log (mn))$ 和 $O(m+n)$ 哪个更优？

取决于 $m$ 和 $n$ 的大小关系：

• 如果 $m=n$（方阵）：$O(\log (n^2))=O(2\log n)=O(\log n)$ vs $O(2n)=O(n)$，二分更快
• 即使 $m\ne n$：$\log (mn)=\log m+\log n<m+n$（当 $m,n\ge 2$ 时始终成立）
• 因此对于 LeetCode 74 的场景，$O(\log (mn))$ 严格优于 $O(m+n)$

但 LeetCode 240 的矩阵不满足 LeetCode 74 的”全局有序”约束，无法做一维二分，只能退而求其次用 $O(m+n)$。

---

第 3 章 旋转数组和矩阵查找的共同思维

3.1 打破”有序才能二分”的思维定势

初学者通常认为”二分查找要求全局有序”。这两道题告诉我们：只要能在每次二分时确定性地排除一半区间，就可以用二分思想。

旋转数组的处理思路：全局有序被破坏 → 但局部有序仍然存在 → 利用局部有序判断 target 在哪一侧 → 二分

矩阵的处理思路（弱有序）：无法全局二分 → 但从特定角落出发，每步都能排除一行或一列 → 线性扫描

本质上，它们都是”利用已知的有序性，做确定性的排除”。只是排除的粒度不同：二分每次排除一半，Z 字形每次排除一行或一列。

3.2 面试中遇到”有序性被干扰”问题的思维步骤

1. 确认有序性的范围：是全局有序？局部有序？行列有序？
2. 找到确定性排除的条件：在什么情况下，可以确定 target 不在某个区间/行/列中？
3. 根据排除条件设计算法：是二分（排除一半）、Z 字形（排除一行/列），还是其他方式？

---

小结

本文讲解了两类”有序性被部分破坏”的查找问题：

旋转有序数组：

• 无重复（LeetCode 33）：利用”mid 必有一半有序”的性质，每次确定有序的那一半，判断 target 是否在其中，决定搜索方向。时间 $O(\log n)$。
• 有重复（LeetCode 81）：当 nums[left] == nums[mid] 时无法判断，只能 left++ 缩小问题，最坏退化为 $O(n)$。

有序矩阵：

• 强有序（LeetCode 74）：矩阵可展开为全局有序数组，直接做一维二分。时间 $O(\log (mn))$。
• 弱有序（LeetCode 240）：从右上角（或左下角）出发，利用”当前元素是该行最大值也是该列最小值”的性质，每步排除一行或一列。时间 $O(m+n)$。

面试核心：二分不是”数组有序才能用”，而是”只要能确定性地排除一半，就能用”。

---

上一篇：05 二分查找核心模板：从基础到左右边界锁定 下一篇：07 快速选择与 TopK 问题：期望 O(n) 的奇妙算法