C++で最小限の比較回数により3つの値の中央値を求める方法

この記事では、与えられた3つの値を比較することで、その中間（中央）の値を求める方法を解説します。例えば、3つの数値 (10, 30, 20) が与えられた場合、中央の値である 20 を返します。まずアルゴリズムの流れを確認し、その後、実際にC++コードとして実装していきましょう。

アルゴリズム

3つの値 a, b, c の中間値を求める手順は以下の通りです。ポイントは、比較を最小限の回数（最大でも3回）で済ませることにあります。

middle_of_three(a, b, c):
入力: 3つの数値 a, b, c
出力: これらの中間値
Begin
    if a > b, then
        if b > c, then
            return b
        else if a > c, then
            return c
        else
            return a
    else
        if a > c, then
            return a
        else if b > c, then
            return c
        else
            return b
End

アルゴリズムの考え方

まず a と b を比較し、大きい方を基準に判断を進めます。

• a > b の場合： さらに b と c を比較します。b > c であれば、a > b > c の順序となるため b が中間値です。そうでなければ a と c を比較し、a > c なら c が、そうでなければ a が中間値となります。
• a ≤ b の場合： a と c を比較します。a > c であれば、c < a ≤ b となるため a が中間値です。そうでなければ b と c を比較し、b > c なら c が、そうでなければ b が中間値となります。

このように条件分岐を工夫することで、ソートを行わずに効率的に中央値を求められます。

C++での実装例

#include <iostream>
using namespace std;

int mid_three(int a, int b, int c) {
    if (a > b) {
        if (b > c)
            return b;
        else if (a > c)
            return c;
        else
            return a;
    } else {
        if (a > c)
            return a;
        else if (b > c)
            return c;
        else
            return b;
    }
}

int main() {
    int a = 10, b = 30, c = 20;
    cout << "Middle Out of Three " << mid_three(a, b, c);
    return 0;
}

実行結果

Middle Out of Three 20

まとめ

このアルゴリズムでは、最良の場合2回、最悪の場合でも3回の比較で3つの値の中間値を求めることができます。3つの値を完全にソートする必要がないため、非常に効率的な手法です。同様のロジックは、クランプ処理（値を一定範囲に収める処理）やメディアンフィルタなどの実装にも応用できます。