C++でソート済み2つのリストの中央値を求める方法【二分探索による効率的な実装】

2つのソート済みリストが与えられたとき、それらを統合した結果の中央値を求める問題を考えます。例えば、配列が [1,5,8] と [2,3,6,9] の場合、統合すると [1,2,3,5,6,8,9] となり、中央値は 5 になります。

この問題は、二分探索を利用することで非常に効率的に解くことができます。単純に2つの配列をマージしてから中央値を計算する方法では O((m+n) log(m+n)) の計算量が必要ですが、分割位置（パーティション）を二分探索で調整する手法を使えば、O(log(min(m, n))) まで削減できます。

アルゴリズムの手順

• solve() 関数を定義します。引数として配列 nums1 と nums2 を受け取ります。
• nums1 のサイズが nums2 より大きい場合は、solve(nums2, nums1) を呼び出して順序を入れ替えます（常に小さい方の配列を基準に探索するため）。
• x := nums1 のサイズ、y := nums2 のサイズ
• low := 0、high := x
• totalLength := x + y
• low ≤ high である間、以下を繰り返します。
  • partitionX := low + (high − low) / 2
  • partitionY := (totalLength + 1) / 2 − partitionX
  • maxLeftX := （partitionX が 0 の場合は −∞、それ以外は nums1[partitionX − 1]）
  • minRightX := （partitionX が x の場合は +∞、それ以外は nums1[partitionX]）
  • maxLeftY := （partitionY が 0 の場合は −∞、それ以外は nums2[partitionY − 1]）
  • minRightY := （partitionY が y の場合は +∞、それ以外は nums2[partitionY]）
  • maxLeftX ≤ minRightY かつ maxLeftY ≤ minRightX を満たす場合（正しい分割が見つかった状態）：
    • totalLength が偶数なら、(max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2 を返す
    • 奇数なら、max(maxLeftX, maxLeftY) を返す
  • そうでなく maxLeftX > minRightY の場合は、high := partitionX − 1 として左側へ探索範囲を狭める
  • それ以外の場合は、low := partitionX + 1 として右側へ探索範囲を狭める
• ループを抜けた場合は 0 を返します（不正な入力に対するフォールバック）。

C++での実装例

以下のコードで実際の動作を確認できます。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    double solve(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size())
            return solve(nums2, nums1);
        int x = nums1.size();
        int y = nums2.size();
        int low = 0;
        int high = x;
        int totalLength = x + y;
        while (low <= high) {
            int partitionX = low + (high - low) / 2;
            int partitionY = (totalLength + 1) / 2 - partitionX;

            int maxLeftX  = (partitionX == 0 ? INT_MIN : nums1[partitionX - 1]);
            int minRightX = (partitionX == x ? INT_MAX : nums1[partitionX]);

            int maxLeftY  = (partitionY == 0 ? INT_MIN : nums2[partitionY - 1]);
            int minRightY = (partitionY == y ? INT_MAX : nums2[partitionY]);

            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                if (totalLength % 2 == 0) {
                    return ((double)max(maxLeftX, maxLeftY)
                          + (double)min(minRightX, minRightY)) / 2;
                }
                else {
                    return max(maxLeftX, maxLeftY);
                }
            }
            else if (maxLeftX > minRightY)
                high = partitionX - 1;
            else
                low = partitionX + 1;
        }
        return 0;
    }
};

int main() {
    Solution ob;
    vector<int> v1 = {1, 5, 8}, v2 = {2, 3, 6, 9};
    cout << ob.solve(v1, v2);
}

入力

[1,5,8], [2,3,6,9]

出力

5

仕組みのポイント

このアルゴリズムの核心は、「小さい方の配列に対してのみ二分探索を行う」点にあります。partitionX を決めると、全体の半分の要素数から自動的に partitionY が決まります。そして「左側の最大値が右側の最小値以下」という条件が両方の配列で成り立てば、その分割が正しい中央値の境界であることが保証されます。

境界条件（partition が 0 または配列末尾）では、それぞれ −∞（INT_MIN）や +∞（INT_MAX）を代入することで、比較処理を例外なく統一的に扱えるのが巧妙な点です。

計算量

• 時間計算量： O(log(min(m, n))) — 小さい方の配列に対してのみ二分探索を行うため
• 空間計算量： O(1) — 追加の配列を作成せず、定数個の変数のみを使用

LeetCode の「Median of Two Sorted Arrays」などでも頻出のテクニックなので、ぜひマスターしておきましょう。