2つのソート済み配列の中央値を求める方法【C++実装付き解説】

中央値（メジアン）とは

中央値とは、データを昇順に並べたときにちょうど中央に位置する値のことです。累積的な割合でいえば、全体の50%の位置に相当する値であり、統計やデータ分析において最も基本的な指標の一つとされています。

本記事では、「サイズが同じ2つのソート済み配列」から中央値を求めるアルゴリズムを紹介します。まずそれぞれの配列単体の中央値を求め、それらを比較しながら絞り込みを行うことで、2つの配列全体の実際の中央値を効率よく導き出します。

入力と出力の例

入力:
ソート済みの2つの配列が与えられます。
Array 1: {1, 2, 3, 6, 7}
Array 2: {4, 6, 8, 10, 11}

出力:
2つの配列から求めた中央値。この場合、中央値は 6 です。

考え方としては、まず2つの配列を1つにマージします。

{1, 2, 3, 4, 6, 6, 7, 8, 10, 11}

この結合後のリストに対して、中央に位置する2つの要素の平均を計算すると、(6 + 6) / 2 = 6 となり、これが求める中央値です。

アルゴリズム

median(list, n)

入力： データのリストとデータ数 n。

出力： 与えられたリストの中央値。

Begin
    if リストのデータ数が偶数ならば
        return (list[n/2] + list[n/2 - 1]) / 2
    else
        return list[n/2]
End

findMedian(list1, list2, n)

入力： ソート済みの2つのリストと、各リストのデータ数 n。

出力： 2つのソート済みリストから求めた中央値。

Begin
    if n <= 0 ならば
        不正な入力として、無効な値を返す
    if n = 1 ならば
        return (list1[0] + list2[0]) / 2
    if n = 2 ならば
        return ((max of list1[0], list2[0]) + (min of list1[1], list2[1])) / 2

    med1 := median(list1, n)
    med2 := median(list2, n)

    if med1 = med2 ならば
        return med1
    if med1 < med2 ならば
        中央側の範囲を切り詰めて再帰的に findMedian を呼び出す
    （med1 > med2 の場合は逆に同様の処理を行う）
End

この手法のポイントは、2つの配列それぞれの中央値を比較することで、探索対象となる要素の範囲を半分ずつに絞り込んでいく点にあります。これにより、全要素をマージしてソートし直すよりもはるかに効率的に中央値を求められます。

C++による実装例

#include<iostream>
using namespace std;

// 単一の配列から中央値を求める関数
int median(int list[], int n) {
    if (n % 2 == 0)   // データ数が偶数の場合
        return (list[n/2] + list[n/2 - 1]) / 2;
    else              // データ数が奇数の場合
        return list[n/2];
}

// 2つの配列から中央値を求める再帰関数
int findMedian(int list1[], int list2[], int n) {
    if (n <= 0)
        return -1;    // リスト長が不正な場合
    if (n == 1)
        return (list1[0] + list2[0]) / 2;  // 要素が1つならその平均
    if (n == 2)
        return (max(list1[0], list2[0]) + min(list1[1], list2[1])) / 2;

    int med1 = median(list1, n);   // 1つ目の配列の中央値
    int med2 = median(list2, n);   // 2つ目の配列の中央値

    if (med1 == med2)  // 中央値が一致すればそれが答え
        return med1;

    if (med1 < med2) {
        // 中央より小さい側を捨てて範囲を絞り込む
        if (n % 2 == 0)
            return findMedian(list1 + n/2 - 1, list2, n - n/2 + 1);
        return findMedian(list1 + n/2, list2, n - n/2);
    }

    // med1 > med2 の場合
    if (n % 2 == 0)
        return findMedian(list2 + n/2 - 1, list1, n - n/2 + 1);
    return findMedian(list2 + n/2, list1, n - n/2);
}

int main() {
    int list1[] = {1, 2, 3, 6, 7};
    int list2[] = {4, 6, 8, 10, 11};

    int n1 = 5;
    int n2 = 5;

    if (n1 == n2)
        cout << "Median is " << findMedian(list1, list2, n1);
    else
        cout << "Doesn't work for lists of unequal size";
}

実行結果

Median is 6

まとめ

このアルゴリズムは、両配列の中央値を繰り返し比較することで不要な範囲を排除し、再帰的に解を求める「分割統治法」的なアプローチです。ただし注意点として、この実装は2つの配列のサイズが等しい場合にのみ正しく動作します。サイズが異なる配列に対しては、別途マージ処理や二分探索を用いた手法（時間計算量 O(log(min(n, m))) の方法など）を検討する必要があります。