雙有序陣列第 N 大元素：二分折疊查找算法深度解析

問題定義

給定兩個長度均為 n 的升序整數陣列 A、B，求這 2n 個元素中第 n 大（即中位數）的值。推廣至任意長度 m, n 及任意順位 k。

核心思想：對稱縮減搜索空間

1. 雙指標分別指向兩陣列尾部 p = A+n, q = B+n。
2. 每輪向前跨越 range = (k+1)/2 步，比較 *p1 與 *q1。
3. 較大者所在陣列的尾部 range 個元素「不可能」包含答案，直接捨棄，k -= range。
4. 另一陣列從尾部向前掃描，跳過所有仍大於該基準值的元素，同步遞減 k。
5. 重複直到 k ≤ 1，最後在常數時間內決出勝負。

等長版本核心代碼

int search4n(int *a, int *b, int n) {
    int *p=a+n, *q=b+n, range;
    if (a[0] > b[n-1]) return a[0];
    if (b[0] > a[n-1]) return b[0];
    while (n > 1) {
        range = (n+1)/2;
        int *p1 = p-range, *q1 = q-range;
        if (*p1 > *q1) {
            n -= range; p = p1; q--;
            while (*q > *p1) { q--; n--; }
        } else {
            n -= range; q = q1; p--;
            while (*p > *q1) { p--; n--; }
        }
    }
    return (n==0) ? max(*p,*q) : max(*--p,*--q);
}

任意長度推廣版

增加邊界檢查 p1 > a、q1 > b，並處理其中一陣列耗盡的情況。邏輯同樣以「雙指標對稱收斂」為核心，額外判斷僅在接近邊界時生效。

複雜度分析

• 空間：O(1)，僅 4 指標 + 1 整數。
• 時間：最佳 O(1)（邊界條件即決）；最差介於 O(log n) 到 O(n) 之間。遞迴式 f(n) = 1 + k + f(n - (n+1)/2 - k)，k 分布決定平均性能，作者未給出閉式解。

優化方向與已知限制

• 可改為迭代避免遞迴開銷。
• 若僅求中位數，經典「二分刪除法」O(log n) 更優。
• 鏈表結構下無法隨機存取，效率大幅下降。
• 代碼中邊界條件極多，實戰建議加入詳盡單元測試覆蓋極端案例（重複值、單元素、全大/全小）。

此算法展示了「對稱雙指標 + 幂級跨越」的巧思，適合作為面試進階題或教學案例，但在生產環境建議採用標準庫 std::nth_element 或經典二分法以求穩健。