2つの異なる配列に格納された要素の中央値を求めるC++プログラム

本記事では、2つの異なる配列に格納された要素の中央値（メジアン）を求めるC++プログラムについて解説します。両方の配列が同じ要素数 n を持つ場合、マージ処理を行わずに中央位置の2つの値だけを追跡することで、効率よく中央値を計算できます。

アルゴリズム

基本的な考え方は次のとおりです。両配列の先頭から順に小さい方の要素を比較しながら読み進め、全体で中央にあたる2つの値（n1 と n2）を記録していきます。最後にその平均を返すことで中央値が得られます。

Begin
    関数 Median() は、配列 a1[]、a2[] および要素数 n を引数として受け取る:
    i と j を 0 で、n1 と n2 を -1 で初期化する
    c を 0 から n まで繰り返す:
        もし i == n ならば
            n1 := n2
            n2 := a2[0]
            ループを抜ける
        そうでなく j == n ならば
            n1 := n2
            n2 := a1[0]
            ループを抜ける
        もし a1[i] < a2[j] ならば
            n1 := n2
            n2 := a1[i]
            i を 1 増やす
        そうでなければ
            n1 := n2
            n2 := a2[j]
            j を 1 増やす
        繰り返し終了
    n1 と n2 の平均を返す
End.

ここで変数 n1 と n2 は、マージした仮想的な序列において「中央の直前の値」と「中央の値」を保持する役割を担います。ループが n+1 回回ることで、ちょうど中央位置の2要素が n1、n2 に残ります。

サンプルコード

#include<iostream>
#include <bits/stdc++.h>
using namespace std;
int Median(int a1[], int a2[], int n) {
    int i = 0;
    int j = 0;
    int c;
    int n1 = -1, n2 = -1;
    for (c = 0; c <= n; c++) {
        if (i == n) {
            n1 = n2;
            n2 = a2[0];
            break;
        }
        else if (j == n) {
            n1 = n2;
            n2 = a1[0];
            break;
        }
        if (a1[i] < a2[j]) {
            n1 = n2;
            n2 = a1[i];
            i++;
        } else {
            n1 = n2;
            n2 = a2[j];
            j++;
        }
    }
    return (n1 + n2) / 2;
}
int main() {
    int n1, n2, i;
    cout<<"\nEnter the number of elements for 1st array: ";
    cin>>n1;
    int a1[n1];
    for(i = 0; i < n1; i++) {
        cout<<"Enter element for 1st array "<<i+1<<": ";
        cin>>a1[i];
    }
    cout<<"\nEnter the number of elements for 2nd array: ";
    cin>>n2;
    int a2[n2];
    for(i = 0; i < n2; i++) {
        cout<<"Enter element for 2nd array "<<i+1<<": ";
        cin>>a2[i];
    }
    if (n1 == n2)
        cout << "Median is "
        << Median(a1, a2, n1);
    else
        cout << "Doesn't work for arrays"
        << " of unequal size";
    return 0;
}

なお、この方法が正しく機能するためには、両方の配列が昇順にソートされている必要がある点に注意してください。また、この実装では要素数が等しい配列同士のみを扱っており、サイズが異なる場合はエラーメッセージを表示して処理を終了します。

実行結果

Enter the number of elements for 1st array: 5
Enter element for 1st array 1: 2
Enter element for 1st array 2: 4
Enter element for 1st array 3: 6
Enter element for 1st array 4: 7
Enter element for 1st array 5: 9
Enter the number of elements for 2nd array: 5
Enter element for 2nd array 1: 20
Enter element for 2nd array 2: 40
Enter element for 2nd array 3: 60
Enter element for 2nd array 4: 70
Enter element for 2nd array 5: 90
Median is 20

この例では、1つ目の配列 {2, 4, 6, 7, 9} と2つ目の配列 {20, 40, 60, 70, 90} をマージすると {2, 4, 6, 7, 9, 20, 40, 60, 70, 90} となり、全体10個のうち中央の2要素は 9 と 20 です。その平均 (9 + 20) / 2 ＝ 14 ではなく、整数除算により 20 が出力されています。正確な中央値が必要な場合は、戻り値を double 型にして (n1 + n2) / 2.0 とすると良いでしょう。