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循环结束仍未找到 → 返回-1153. 寻找旋转排序数组中的最小值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]。算法步骤确保短数组在前交换nums1和nums2令nums1长度m更小减少循环次数。初始化边界left 0,right m。二分查找分割点ii (left right) / 2nums1的分割点j (m n 1) / 2 - inums2的分割点处理边界若i 0nums1左最大值为-∞若i mnums1右最小值为∞。同理处理j。调整范围若nums1[i-1] nums2[j]→i太大向左移动right i - 1若nums2[j-1] nums1[i]→i太小向右移动left i 1找到正确分割点退出循环。计算中位数总长度奇数中位数 左半部分最大值 (max(nums1[i-1], nums2[j-1]))总长度偶数中位数 (左半最大值 右半最小值) / 2class 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[i1] 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]m1n2。步骤 2给数组加 “哨兵”避免越界麻烦原数组的边界判断很头疼比如nums1里没元素进左半时没法取 “左半最后一个元素”所以代码新建了两个数组a和b在数组最左边加Integer.MIN_VALUE负无穷最右边加Integer.MAX_VALUE正无穷把原数组内容塞到中间。示例交换后的nums1[2]→ 新数组a [-∞, 2, ∞]nums2[1,3]→ 新数组b [-∞, 1, 3, ∞]不管怎么取位置都不会出现 “数组越界” 的问题。步骤 3初始化分割点确定左右半的元素个数我们要让左半部分总共有(mn1)/2个元素统一奇数 / 偶数的计算设inums1里进左半的元素个数jnums2里进左半的元素个数初始时i0nums1里 0 个元素进左半j(mn1)/2 (121)/22nums2里 2 个元素进左半。示例初始i0j2→ 左半是nums1的 0 个 nums2的 2 个即[1,3]右半是nums1的 1 个即[2] nums2的 0 个。步骤 4枚举找最优分割点核心循环判断能不能把nums1里再多一个元素放进左半判断条件a[i1] b[j]→ 意思是 “nums1下一个要进左半的元素比nums2左半最后一个元素小 / 等于”说明可以放心把这个元素放进左半每满足一次就把i1nums1多 1 个进左半j-1nums2少 1 个进左半直到条件不满足此时的i就是最优分割点。示例初始i0j2→a[1]2nums1下一个元素 ≤b[2]3nums2左半最后一个→ 满足执行i1j1→ 现在左半是nums1的 1 个[2] nums2的 1 个[1]右半是nums1的 0 个 nums2的 1 个[3]再判断a[2]∞nums1下一个元素 ≤b[1]1不满足 → 循环停止最优分割点是i1j1。步骤 5计算中位数左半最大值 max(a[i], b[j])→ 示例中max(a[1]2, b[1]1) 2右半最小值 min(a[i1], b[j1])→ 示例中min(a[2]∞, b[2]3) 3总长度是123奇数→ 中位数就是左半最大值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否则最小值在左半区含 midright mid循环条件left right最终left right时即为最小值下标。3. 寻找两个正序数组的中位数LeetCode 4提供两种核心解法均围绕 “分割数组为左右两半左半总长度为(mn1)/2且左半最大值 ≤ 右半最小值” 的中位数本质解法 1二分查找保证短数组为nums1以减少二分次数二分查找nums1的分割点i对应nums2分割点j (mn1)/2 - i通过边界值正负无穷处理越界找到满足nums1[i-1] ≤ nums2[j]且nums2[j-1] ≤ nums1[i]的分割点计算中位数。解法 2顺序枚举给数组加 “哨兵正负无穷” 避免边界判断枚举nums1的分割点i找到满足a[i1] b[j]的临界值取左半最大值和右半最小值根据总长度奇偶计算中位数。关键点回顾旋转有序数组问题的核心是判断有序区间利用有序区间的单调性缩小查找范围两个正序数组的中位数问题本质是找到合法分割点让左右两半满足 “左小右大” 且长度均衡二分查找的优化技巧缩短目标数组长度、加哨兵处理边界、统一奇偶场景的计算逻辑。