题目描述#

给定两个分别已经升序排好的数组 nums1 和 nums2，长度分别为 m 和 n，要找出这两个数组合在一起之后的中位数。题目对时间复杂度卡得很死，要求 O(log(m+n))，所以"合并再排序"的偷懒解法直接被毙掉啦——只能上二分。

两个数组都是排好序的，可中位数偏偏要"合并视角"才能看到，咱得想个办法不真合并它们……

思路#

中位数的本质，就是把整个有序集合"砍成左右两半"的那条分界线：左半部分的元素个数固定，并且左半的最大值不超过右半的最小值。这道题之所以能用二分，就是因为只要在 nums1 上选一个切点，nums2 的切点就被反向锁死了——两边的切位置一旦同步，分界线也就唯一确定了。

设咱从 a（短的那个）切走 i 个元素到左半部分，那么 b 必须切走 j = (m+n+1)/2 - i 个，左半总数才刚好是 (m+n+1)/2。这种取整方式很关键：当 m+n 为奇数时，左半比右半多一个，中位数就是左半最大值；为偶数时左右等长，中位数取左半最大与右半最小的平均。所以无论奇偶，都用同一套切法处理就行。

二分的对象就是 i，范围 [0, m]。咱只判定一个方向的不等式：a[i] <= b[j+1]。如果成立，说明 a 这边还有空间多切一格，lo = i + 1；不成立则 hi = i - 1。循环结束后的 hi，就是最大的满足条件的 i。为什么单边判定就够？因为 i 增大时 a[i] 单调不减、b[j+1] 单调不增，两者一旦交叉，再增大 i 就会破坏另一侧的约束，所以"最大可行 i“就是答案。

至于代码里两头加 MinInt / MaxInt 的小技巧——这是用哨兵把 i = 0（a 一个都不切）和 i = m（a 全切走）这两种边界情况吞掉。没有哨兵就得在循环里写一堆 if i == 0、if i == m+1，加了哨兵之后所有比较都"自然成立或自然不成立”，循环体能保持干干净净。还有个细节是先把短数组挪到 a 上，这样二分范围最小，复杂度才能压到 O(log min(m, n))。

照片当然不是现实，但如果两个数组的分界拍准了，是不是就离正中间那一帧更近一些呢？

思维边界#

• 二分对象是切点 i，不是某个具体的数值；这一类二分问题都属于"二分答案的索引"。
• 必须二分较短的数组：保证 i ∈ [0, m] 范围最小，且 j = (m+n+1)/2 - i 不会出现负数。
• (m+n+1)/2 的取整方式让奇偶情况能合并处理——左半始终比右半多 0 或 1 个。
• 哨兵 MinInt / MaxInt：消掉了 i == 0 与 i == m 的边界判断；带哨兵后下标整体右移一位，a[i] 实际指代的是"切完之后 a 左半的最大值"。
• 单边判定：只看 a[i] <= b[j+1] 即可，因为另一侧约束 b[j] <= a[i+1] 会在最优 i 处自动成立。
• 循环结束时用的是 hi 不是 lo：因为最后那一步可能让 lo 越过了正确答案，hi 才是最大的可行 i。
• 答案要返回 float64：偶数长度时要除 2，整数除法会丢精度，所以先转浮点再相加除 2。

本姑娘小结：二分短数组、加哨兵免边界、单边判定取最大 `i`，困难题就这么被偷走啦～

代码#

import "math"

func findMedianSortedArrays(a []int, b []int) float64 {
    if len(a) > len(b) {
        a, b = b, a
    }
    m, n := len(a), len(b)
    a = append([]int{math.MinInt}, append(a, math.MaxInt)...)
    b = append([]int{math.MinInt}, append(b, math.MaxInt)...)

    lo, hi := 0, m
    for lo <= hi {
        i := (lo + hi) / 2
        j := (m+n+1)/2 - i
        if a[i] <= b[j+1] {
            lo = i + 1 // 前进一步，不会死循环
        } else {
            hi = i - 1 // 后退一步
        }
    }
    // 结束时 hi 就是最大的满足 a[i] <= b[j+1] 的 i
    i := hi

    // 循环结束，lo 就是最大的满足 a[i] <= b[j+1] 的 i
    j := (m+n+1)/2 - i
    max1 := max(a[i], b[j])
    min2 := min(a[i+1], b[j+1])
    if (m+n)%2 > 0 {
        return float64(max1)
    }
    return float64(max1+min2) / 2
}