同じサイズの2つのソート済み配列の中央値を求めるC/C++プログラム

本記事では、同じサイズを持つ2つのソート済み配列から中央値を求める方法を解説します。配列要素の格納にはC++のSTL（標準テンプレートライブラリ）を使用します。2つの配列を受け取ったら、それらを1つにマージします。同じサイズの配列同士を結合すると、最終的な配列は必ず偶数個の要素を持つことになります。そのため、中央の2つの要素を取り出し、その平均値を中央値として計算します。

アルゴリズム

median(arr1, arr2)

Begin
    arr3 := arr1とarr2をマージした後の配列
    arr3をソートする
    len := arr3の長さ
    mid := len/2
    median := (arr3[mid] + arr3[mid-1])/2
    return median
End

サンプルコード

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
float median(vector<int> arr1, vector<int> arr2) {
    vector arr3(arr1.size() + arr2.size());
    merge(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), arr3.begin());
    sort(arr3.begin(), arr3.end());
    int len = arr3.size();
    int mid = len/2;
    return float(arr3[mid] + arr3[mid-1])/2;
}
main() {
    vector<int> arr1 = {1, 3, 4, 6, 7};
    vector<int> arr2 = {4, 5, 7, 8, 9};
    cout << "Median: " << median(arr1, arr2);
}

実行結果

Median: 5.5

処理の流れの解説

このプログラムでは、まずSTLのmerge関数を使って、2つのソート済み配列arr1とarr2を効率的に1つの配列arr3へ統合しています。merge関数は両方の入力がソート済みであることを前提としているため、全体を一からソートするよりも高速に動作します。念のためsort関数で並べ替えを行った後、配列の長さを取得し、中央インデックスmid（len/2）を計算します。

マージ後の配列は10個の要素（偶数）を持つため、中央値は9番目と10番目の要素（インデックス4と5）の平均となります。上記の例では、マージ後の配列は {1, 3, 4, 4, 5, 6, 7, 7, 8, 9} となり、中央の2つの要素は5と6です。したがって、(5 + 6) / 2 = 5.5 が中央値として出力されます。