二分探索を用いた2つのソート済み配列の中央値の求め方（C++実装）

2つのソート済み配列をマージせずに中央値を求めるには、二分探索を応用した分割統治法が効率的です。時間計算量は O(log(min(m,n))) で実現できます。ここでは、同じサイズの2つの配列に対する基本的なアプローチを C++ で実装し、アルゴリズムの流れとコード例を解説します。

アルゴリズムの概要

1. 各部分配列の開始インデックスと終了インデックスを引数に median() 関数を呼び出す。
2. 部分配列の長さを e1 - s1 + 1 で計算する。
3. 長さが 1 または 2 の場合（基本ケース）、直接中央値を計算して返す。
4. 両配列の中央値 m1, m2 を比較する。
   • m1 == m2 ならそれが全体の中央値。
   • m1 > m2 なら、第1配列の前半と第2配列の後半に中央値が存在する。
   • m1 < m2 なら、第1配列の後半と第2配列の前半に中央値が存在する。
5. 探索範囲を半分に絞り込み、再帰的に median() を呼び出す。

実装例（C++）

#include <iostream>
using namespace std;

// 2つの同サイズ配列 a1[s1..e1], a2[s2..e2] の中央値を求める
void median(float a1[], int s1, int e1, float a2[], int s2, int e2) {
    float m1, m2;
    int len = e1 - s1 + 1;

    if (len % 2 == 0) {           // 偶数長
        if (len == 2) {           // 基本ケース：要素数2
            m1 = (min(a1[s1], a2[s2]) + max(a1[e1], a2[e2])) / 2.0f;
            cout << m1;
            return;
        }
        m1 = (a1[(s1 + e1) / 2] + a1[(s1 + e1) / 2 + 1]) / 2.0f;
        m2 = (a2[(s2 + e2) / 2] + a2[(s2 + e2) / 2 + 1]) / 2.0f;
    } else {                      // 奇数長
        if (len == 1) {           // 基本ケース：要素数1
            m1 = (a1[s1] + a2[s2]) / 2.0f;
            cout << m1;
            return;
        }
        m1 = a1[(s1 + e1) / 2];
        m2 = a2[(s2 + e2) / 2];
    }

    if (m1 == m2) {               // 中央値が一致
        cout << m1;
        return;
    }

    if (m1 > m2) {
        // a1 の前半、a2 の後半を残す
        median(a1, s1, (s1 + e1) / 2 + (len % 2 == 0 ? 1 : 0),
               a2, (s2 + e2) / 2, e2);
    } else {
        // a1 の後半、a2 の前半を残す
        median(a1, (s1 + e1) / 2, e1,
               a2, s2, (s2 + e2) / 2 + (len % 2 == 0 ? 1 : 0));
    }
}

int main() {
    int n1, n2;
    cout << "1つ目の配列の要素数: ";
    cin >> n1;
    float a1[n1];
    for (int i = 0; i < n1; ++i) {
        cout << "要素 " << i + 1 << ": ";
        cin >> a1[i];
    }

    cout << "2つ目の配列の要素数: ";
    cin >> n2;
    float a2[n2];
    for (int i = 0; i < n2; ++i) {
        cout << "要素 " << i + 1 << ": ";
        cin >> a2[i];
    }

    if (n1 != n2) {
        cout << "この実装では両配列のサイズが等しい必要があります。\n";
        return 1;
    }

    cout << "中央値: ";
    median(a1, 0, n1 - 1, a2, 0, n2 - 1);
    cout << endl;
    return 0;
}

実行例

1つ目の配列の要素数: 5
要素 1: 6
要素 2: 7
要素 3: 9
要素 4: 10
要素 5: 11
2つ目の配列の要素数: 5
要素 1: 60
要素 2: 70
要素 3: 90
要素 4: 100
要素 5: 110
中央値: 35

補足と改善ポイント

• 元のサンプルコードには、2つ目の配列入力時に a1[i] へ書き込んでいるバグがありました。上記では修正済みです。
• この実装は「要素数が等しい2配列」専用です。異なるサイズに対応するには、より一般的な「パーティション法（二分探索で分割点を探す）」を用いるのが定石です。
• 実用的には std::vector とイテレータ、あるいは std::median (C++26予定) などを活用するとより堅牢になります。