二分查找在中位数与两有序数组中的极限应用LeetCode 4 题推导在 LeetCode 算法题库中第 4 题“寻找两个正序数组的中位数Median of Two Sorted Arrays”被公认为二分查找领域的“封神之题”。题目要求在严格的 $O(\log(\min(m, n)))$ 时间复杂度内求出中位数。很多同学虽然能写出双指针合并数组的 $O(m n)$ 解法但在面试官限定“必须对数级时间复杂度且不能开辟额外空间”的硬性要求下往往在多层划分和边界指针的交叉验证上彻底迷失。今天我们用几何切分模型与虚拟边界法把这道题的二分推导逻辑彻底理顺。问题转化从“找中位数”到“寻找第 K 小元素”与“数组完美划分”设两个升序数组分别为 $A$长度 $m$和 $B$长度 $n$。假设 $m \le n$若不满足交换 $A$ 和 $B$ 即可保证对较短数组进行二分。求中位数本质上是在数组 $A$ 和 $B$ 中各切一刀数组 $A$ 在下标 $i$ 处切开分成左半部分 $A[0 \dots i-1]$ 和右半部分 $A[i \dots m-1]$数组 $B$ 在下标 $j$ 处切开分成左半部分 $B[0 \dots j-1]$ 和右半部分 $B[j \dots n-1]$。我们将 $A$ 的左半部分和 $B$ 的左半部分合并为“总左半区”将 $A$ 的右半部分和 $B$ 的右半部分合并为“总右半区”。中位数的充要条件只有两个元素数量平衡总左半区的元素数量等于总右半区当 $mn$ 为偶数时或者比右半区多 1当 $mn$ 为奇数时。$$\text{左半区长度 } i j \frac{m n 1}{2} \implies j \frac{m n 1}{2} - i$$这意味着只要 $i$ 确定了$j$ 就会被严格唯一确定数值交叉有序总左半区的最大值必须 $\le$ 总右半区的最小值。由于 $A$ 和 $B$ 自身已经有序$A[i-1] \le A[i]$ 且 $B[j-1] \le B[j]$我们只需要保证交叉条件成立$$A[i-1] \le B[j] \quad \text{且} \quad B[j-1] \le A[i]$$graph TD A[在较短数组 A 的 [0, m] 区间二分划分点 i] -- B[由数学公式直接算出 j (mn1)/2 - i] B -- C{A[i-1] B[j] ?} C --|是: A 的划分点太靠右| D[向左收缩: right i - 1] C --|否| E{B[j-1] A[i] ?} E --|是: A 的划分点太靠左| F[向右收缩: left i 1] E --|否: 完美命中| G[根据奇偶性直接计算中位数]虚拟边界处理消除复杂的if-else越界特判当切刀切在数组最边缘时如 $i 0$ 或 $i m$$A[i-1]$ 或 $A[i]$ 会发生数组越界。传统写法需要写一长串冗长的三元表达式。我们可以引入正负无穷虚拟哨兵值若 $i 0$定义 $A[i-1] -\infty$Integer.MIN_VALUE若 $i m$定义 $A[i] \infty$Integer.MAX_VALUE若 $j 0$定义 $B[j-1] -\infty$若 $j n$定义 $B[j] \infty$。这样交叉有序判定直接统一为一行逻辑极其优雅。标准生产级代码落地public class FindMedianSortedArraysSolution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 保证对较短数组进行二分时间复杂度优化为 O(log(min(m, n))) if (nums1.length nums2.length) { return findMedianSortedArrays(nums2, nums1); } int m nums1.length; int n nums2.length; int left 0; int right m; // 划分点 i 可以取 0 到 m共 m1 种可能 int totalLeft (m n 1) / 2; while (left right) { int i left ((right - left) 1); int j totalLeft - i; int nums1LeftMax (i 0) ? Integer.MIN_VALUE : nums1[i - 1]; int nums1RightMin (i m) ? Integer.MAX_VALUE : nums1[i]; int nums2LeftMax (j 0) ? Integer.MIN_VALUE : nums2[j - 1]; int nums2RightMin (j n) ? Integer.MAX_VALUE : nums2[j]; if (nums1LeftMax nums2RightMin nums2LeftMax nums1RightMin) { // 完美划分计算中位数 if ((m n) % 2 1) { return Math.max(nums1LeftMax, nums2LeftMax); } else { return (Math.max(nums1LeftMax, nums2LeftMax) Math.min(nums1RightMin, nums2RightMin)) / 2.0; } } else if (nums1LeftMax nums2RightMin) { // nums1 切得太靠右了需要向左缩 right i - 1; } else { // nums2 切得太靠右nums1 切得太靠左需要向右扩展 left i 1; } } throw new IllegalArgumentException(输入数组不符合升序前置约束); } }复杂度与面试答题技巧时间复杂度只在长度为 $m$ 的数组上做二分每次排除一半区间严格保证 $O(\log(\min(m, n)))$空间复杂度仅使用常数个局部指针与哨兵变量严格为 $O(1)$。在面试现场千万不要直接上手堆代码。先在白板上画出总左半区与总右半区的划分草图写出 $j \frac{mn1}{2} - i$ 的数学约束再给出正负无穷哨兵的处理思路。面试官对你的数学建模与工程实现能力将给予极高的评价。
二分查找在中位数与两有序数组中的极限应用LeetCode 4 题推导在 LeetCode 算法题库中第 4 题“寻找两个正序数组的中位数Median of Two Sorted Arrays”被公认为二分查找领域的“封神之题”。题目要求在严格的 $O(\log(\min(m, n)))$ 时间复杂度内求出中位数。很多同学虽然能写出双指针合并数组的 $O(m n)$ 解法但在面试官限定“必须对数级时间复杂度且不能开辟额外空间”的硬性要求下往往在多层划分和边界指针的交叉验证上彻底迷失。今天我们用几何切分模型与虚拟边界法把这道题的二分推导逻辑彻底理顺。问题转化从“找中位数”到“寻找第 K 小元素”与“数组完美划分”设两个升序数组分别为 $A$长度 $m$和 $B$长度 $n$。假设 $m \le n$若不满足交换 $A$ 和 $B$ 即可保证对较短数组进行二分。求中位数本质上是在数组 $A$ 和 $B$ 中各切一刀数组 $A$ 在下标 $i$ 处切开分成左半部分 $A[0 \dots i-1]$ 和右半部分 $A[i \dots m-1]$数组 $B$ 在下标 $j$ 处切开分成左半部分 $B[0 \dots j-1]$ 和右半部分 $B[j \dots n-1]$。我们将 $A$ 的左半部分和 $B$ 的左半部分合并为“总左半区”将 $A$ 的右半部分和 $B$ 的右半部分合并为“总右半区”。中位数的充要条件只有两个元素数量平衡总左半区的元素数量等于总右半区当 $mn$ 为偶数时或者比右半区多 1当 $mn$ 为奇数时。$$\text{左半区长度 } i j \frac{m n 1}{2} \implies j \frac{m n 1}{2} - i$$这意味着只要 $i$ 确定了$j$ 就会被严格唯一确定数值交叉有序总左半区的最大值必须 $\le$ 总右半区的最小值。由于 $A$ 和 $B$ 自身已经有序$A[i-1] \le A[i]$ 且 $B[j-1] \le B[j]$我们只需要保证交叉条件成立$$A[i-1] \le B[j] \quad \text{且} \quad B[j-1] \le A[i]$$graph TD A[在较短数组 A 的 [0, m] 区间二分划分点 i] -- B[由数学公式直接算出 j (mn1)/2 - i] B -- C{A[i-1] B[j] ?} C --|是: A 的划分点太靠右| D[向左收缩: right i - 1] C --|否| E{B[j-1] A[i] ?} E --|是: A 的划分点太靠左| F[向右收缩: left i 1] E --|否: 完美命中| G[根据奇偶性直接计算中位数]虚拟边界处理消除复杂的if-else越界特判当切刀切在数组最边缘时如 $i 0$ 或 $i m$$A[i-1]$ 或 $A[i]$ 会发生数组越界。传统写法需要写一长串冗长的三元表达式。我们可以引入正负无穷虚拟哨兵值若 $i 0$定义 $A[i-1] -\infty$Integer.MIN_VALUE若 $i m$定义 $A[i] \infty$Integer.MAX_VALUE若 $j 0$定义 $B[j-1] -\infty$若 $j n$定义 $B[j] \infty$。这样交叉有序判定直接统一为一行逻辑极其优雅。标准生产级代码落地public class FindMedianSortedArraysSolution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 保证对较短数组进行二分时间复杂度优化为 O(log(min(m, n))) if (nums1.length nums2.length) { return findMedianSortedArrays(nums2, nums1); } int m nums1.length; int n nums2.length; int left 0; int right m; // 划分点 i 可以取 0 到 m共 m1 种可能 int totalLeft (m n 1) / 2; while (left right) { int i left ((right - left) 1); int j totalLeft - i; int nums1LeftMax (i 0) ? Integer.MIN_VALUE : nums1[i - 1]; int nums1RightMin (i m) ? Integer.MAX_VALUE : nums1[i]; int nums2LeftMax (j 0) ? Integer.MIN_VALUE : nums2[j - 1]; int nums2RightMin (j n) ? Integer.MAX_VALUE : nums2[j]; if (nums1LeftMax nums2RightMin nums2LeftMax nums1RightMin) { // 完美划分计算中位数 if ((m n) % 2 1) { return Math.max(nums1LeftMax, nums2LeftMax); } else { return (Math.max(nums1LeftMax, nums2LeftMax) Math.min(nums1RightMin, nums2RightMin)) / 2.0; } } else if (nums1LeftMax nums2RightMin) { // nums1 切得太靠右了需要向左缩 right i - 1; } else { // nums2 切得太靠右nums1 切得太靠左需要向右扩展 left i 1; } } throw new IllegalArgumentException(输入数组不符合升序前置约束); } }复杂度与面试答题技巧时间复杂度只在长度为 $m$ 的数组上做二分每次排除一半区间严格保证 $O(\log(\min(m, n)))$空间复杂度仅使用常数个局部指针与哨兵变量严格为 $O(1)$。在面试现场千万不要直接上手堆代码。先在白板上画出总左半区与总右半区的划分草图写出 $j \frac{mn1}{2} - i$ 的数学约束再给出正负无穷哨兵的处理思路。面试官对你的数学建模与工程实现能力将给予极高的评价。
