LeetCode 热题 100 之 33. 搜索旋转排序数组 153. 寻找旋转排序数组中的最小值 4. 寻找两个正序数组的中位数

33. 搜索旋转排序数组

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

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

33. 搜索旋转排序数组

class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } // 左半部分有序 if (nums[left] <= nums[mid]) { // target 在左半有序区间内 if (target >= nums[left] && target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } } // 右半部分有序 else { // target 在右半有序区间内 if (target > nums[mid] && target <= nums[right]) { left = mid + 1; } else { right = mid - 1; } } } return -1; } }

解题思路:二分查找

初始化left = 0,right = len(nums) - 1

循环条件：left <= right

取中间值mid = (left + right) // 2：

• 若nums[mid] == target→ 直接返回mid

• 判断左半部分是否有序：nums[left] <= nums[mid]

  • 若左半有序：

    • 若target在[nums[left], nums[mid]]之间 → 目标在左半部分，令right = mid - 1

    • 否则 → 目标在右半部分，令left = mid + 1

  • 若右半部分有序（即左半无序）：

    • 若target在[nums[mid], nums[right]]之间 → 目标在右半部分，令left = mid + 1

    • 否则 → 目标在左半部分，令right = mid - 1

循环结束仍未找到 → 返回-1

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

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

解题思路:二分查找

初始化left = 0,right = len(nums) - 1

循环条件：left < right（避免left == right时死循环）

取中间值mid = (left + right) // 2：

• 若nums[mid] > nums[right]→ 说明最小值在右半部分（因为左半部分有序且整体更大），令left = mid + 1

• 若nums[mid] < nums[right]→ 说明最小值在左半部分（含 mid）（因为右半部分有序且整体更大），令right = mid

循环结束时left == right，该位置即为最小值的下标

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

class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 确保 nums1 是较短的数组，减少二分次数 if (nums1.length > nums2.length) { int[] temp = nums1; nums1 = nums2; nums2 = temp; } int m = nums1.length; int n = nums2.length; int left = 0, right = m; int halfLen = (m + n + 1) / 2; while (left <= right) { int i = (left + right) / 2; // nums1 的分割点 int j = halfLen - i; // nums2 的分割点 // 处理边界值，越界时设为正负无穷 int nums1Left = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1]; int nums1Right = (i == m) ? Integer.MAX_VALUE : nums1[i]; int nums2Left = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1]; int nums2Right = (j == n) ? Integer.MAX_VALUE : nums2[j]; // 找到正确的分割点 if (nums1Left > nums2Right) { right = i - 1; } else if (nums2Left > nums1Right) { left = i + 1; } else { // 计算中位数 if ((m + n) % 2 == 1) { return Math.max(nums1Left, nums2Left); } else { return (Math.max(nums1Left, nums2Left) + Math.min(nums1Right, nums2Right)) / 2.0; } } } return 0.0; // 理论上不会执行到这里 } }

解题思路1:二分查找

中位数的本质是将数据分为上下两部分，满足：

• 左半部分数量 = 右半部分数量（或左多 1）

• 左半部分所有值 ≤ 右半部分所有值

我们将数组nums1在i处分割，数组nums2在j处分割，使得i + j = (m + n + 1) / 2（统一奇偶情况）。最终满足：nums1[i-1] <= nums2[j]且nums2[j-1] <= nums1[i]。

算法步骤

1. 确保短数组在前：交换nums1和nums2，令nums1长度m更小，减少循环次数。

2. 初始化边界：left = 0,right = m。

3. 二分查找分割点i：

   1. i = (left + right) / 2（nums1的分割点）

   2. j = (m + n + 1) / 2 - i（nums2的分割点）

   3. 处理边界：若i == 0，nums1左最大值为-∞；若i == m，nums1右最小值为+∞。同理处理j。

   4. 调整范围：

      • 若nums1[i-1] > nums2[j]→i太大，向左移动，right = i - 1

      • 若nums2[j-1] > nums1[i]→i太小，向右移动，left = i + 1

      • 找到正确分割点，退出循环。

4. 计算中位数：

   1. 总长度奇数：中位数 = 左半部分最大值 (max(nums1[i-1], nums2[j-1]))

   2. 总长度偶数：中位数 = (左半最大值 + 右半最小值) / 2

class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { if (nums1.length > nums2.length) { // 交换 nums1 和 nums2，保证下面的 i 可以从 0 开始枚举 int[] tmp = nums1; nums1 = nums2; nums2 = tmp; } int m = nums1.length; int n = nums2.length; int[] a = new int[m + 2]; int[] b = new int[n + 2]; a[0] = b[0] = Integer.MIN_VALUE; // 最左边插入 -∞ a[m + 1] = b[n + 1] = Integer.MAX_VALUE; // 最右边插入 ∞ System.arraycopy(nums1, 0, a, 1, m); // 数组没法直接插入，只能 copy System.arraycopy(nums2, 0, b, 1, n); // 枚举 nums1 有 i 个数在第一组 // 那么 nums2 有 j = (m + n + 1) / 2 - i 个数在第一组 int i = 0; int j = (m + n + 1) / 2; while (a[i + 1] <= b[j]) { i++; // 继续枚举 j--; } int max1 = Math.max(a[i], b[j]); // 第一组的最大值 int min2 = Math.min(a[i + 1], b[j + 1]); // 第二组的最小值 return (m + n) % 2 > 0 ? max1 : (max1 + min2) / 2.0; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/2950686/tu-jie-xun-xu-jian-jin-cong-shuang-zhi-z-p2gd/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解题思路2:顺序枚举

先保证nums1是更短的数组 → 给两个数组前后加「哨兵（正负无穷）」避免边界判断 → 枚举nums1中进入左半部分的元素个数i，找到满足a[i+1] > b[j]的临界分割点 → 计算中位数。

我们用示例nums1=[1,3]、nums2=[2]来对应每一步，帮你理解：

步骤 1：先让短数组当 “主角”，减少工作量

代码开头先交换nums1和nums2，保证nums1是更短的数组。

• 原因：后面要枚举nums1里有多少元素进左半部分，短数组枚举次数少，比如示例中nums1长度 2，最多枚举 2 次就够了。

• 示例：nums1=[1,3]（长度 2）、nums2=[2]（长度 1），这里nums2更短，交换后nums1=[2]、nums2=[1,3]（m=1，n=2）。

步骤 2：给数组加 “哨兵”，避免越界麻烦

原数组的边界判断很头疼（比如nums1里没元素进左半时，没法取 “左半最后一个元素”），所以代码新建了两个数组a和b：

• 在数组最左边加Integer.MIN_VALUE（负无穷），最右边加Integer.MAX_VALUE（正无穷）；

• 把原数组内容塞到中间。

• 示例：

  • 交换后的nums1=[2]→ 新数组a = [-∞, 2, +∞]；

  • nums2=[1,3]→ 新数组b = [-∞, 1, 3, +∞]；

  • 不管怎么取位置，都不会出现 “数组越界” 的问题。

步骤 3：初始化分割点，确定左右半的元素个数

我们要让左半部分总共有(m+n+1)/2个元素（统一奇数 / 偶数的计算）：

• 设i=nums1里进左半的元素个数，j=nums2里进左半的元素个数；

• 初始时i=0（nums1里 0 个元素进左半），j=(m+n+1)/2 = (1+2+1)/2=2（nums2里 2 个元素进左半）。

• 示例：初始i=0，j=2→ 左半是nums1的 0 个 +nums2的 2 个（即[1,3]），右半是nums1的 1 个（即[2]） +nums2的 0 个。

步骤 4：枚举找最优分割点（核心！）

循环判断：能不能把nums1里再多一个元素放进左半？

• 判断条件：a[i+1] <= b[j]→ 意思是 “nums1下一个要进左半的元素，比nums2左半最后一个元素小 / 等于”，说明可以放心把这个元素放进左半；

• 每满足一次，就把i+1（nums1多 1 个进左半），j-1（nums2少 1 个进左半）；

• 直到条件不满足，此时的i就是最优分割点。

• 示例：

  • 初始i=0，j=2→a[1]=2（nums1下一个元素） ≤b[2]=3（nums2左半最后一个）→ 满足；

  • 执行i=1，j=1→ 现在左半是nums1的 1 个（[2]） +nums2的 1 个（[1]），右半是nums1的 0 个 +nums2的 1 个（[3]）；

  • 再判断：a[2]=+∞（nums1下一个元素） ≤b[1]=1？不满足 → 循环停止，最优分割点是i=1，j=1。

步骤 5：计算中位数

• 左半最大值 =max(a[i], b[j])→ 示例中max(a[1]=2, b[1]=1) = 2；

• 右半最小值 =min(a[i+1], b[j+1])→ 示例中min(a[2]=+∞, b[2]=3) = 3；

• 总长度是1+2=3（奇数）→ 中位数就是左半最大值2；如果是偶数，就取（左半最大值 + 右半最小值）/2。

核心内容总结

本文围绕二分查找解决三类经典有序 / 旋转有序数组问题展开，核心内容如下：

1. 搜索旋转排序数组（LeetCode 33）

• 核心思路：利用旋转数组的特性（必有一半区间是有序的），在二分过程中先判断左 / 右半区是否有序，再根据target是否在有序区间内缩小查找范围，最终找到目标值下标或返回 - 1。
• 关键逻辑：
  • 若左半区（nums[left] <= nums[mid]）有序，判断target是否在[nums[left], nums[mid])内，是则缩右边界，否则缩左边界；
  • 若右半区有序，判断target是否在(nums[mid], nums[right]]内，是则缩左边界，否则缩右边界。

2. 寻找旋转排序数组中的最小值（LeetCode 153）

• 核心思路：简化版二分查找，利用旋转数组 “最小值一定在无序的半区” 特性，通过比较nums[mid]和nums[right]缩小范围：
  • 若nums[mid] > nums[right]，说明最小值在右半区，left = mid + 1；
  • 否则最小值在左半区（含 mid），right = mid；
• 循环条件：left < right，最终left == right时即为最小值下标。

3. 寻找两个正序数组的中位数（LeetCode 4）

提供两种核心解法，均围绕 “分割数组为左右两半，左半总长度为(m+n+1)/2，且左半最大值 ≤ 右半最小值” 的中位数本质：

• 解法 1（二分查找）：
  1. 保证短数组为nums1以减少二分次数；
  2. 二分查找nums1的分割点i，对应nums2分割点j = (m+n+1)/2 - i；
  3. 通过边界值（正负无穷）处理越界，找到满足nums1[i-1] ≤ nums2[j]且nums2[j-1] ≤ nums1[i]的分割点，计算中位数。
• 解法 2（顺序枚举）：
  1. 给数组加 “哨兵（正负无穷）” 避免边界判断；
  2. 枚举nums1的分割点i，找到满足a[i+1] > b[j]的临界值；
  3. 取左半最大值和右半最小值，根据总长度奇偶计算中位数。

关键点回顾

1. 旋转有序数组问题的核心是判断有序区间，利用有序区间的单调性缩小查找范围；
2. 两个正序数组的中位数问题，本质是找到合法分割点，让左右两半满足 “左小右大” 且长度均衡；
3. 二分查找的优化技巧：缩短目标数组长度、加哨兵处理边界、统一奇偶场景的计算逻辑。