C++でソート済み配列から出現頻度がn/2以上の要素を検索する方法

サイズnのソート済み配列を考えます。この配列には、出現回数がn/2以上（nは要素数）となる要素が必ず1つ存在します。例えば、配列が [3, 4, 5, 5, 5] の場合、出力は 5 となります。

解法のポイント

この種の配列を注意深く観察すると、重要な性質に気づくことができます。それは、出現頻度がn/2以上の要素は、必ずインデックス n/2 の位置にも存在するという点です。

なぜなら、ある要素が配列全体の半分以上を占めている場合、その要素は配列の中央位置（n/2）に必ず含まれるからです。したがって、配列がすでにソートされていることを利用すれば、線形探索やハッシュマップを使わずに、単一の要素アクセスだけで目的の要素を見つけることができます。計算量はO(1)と非常に効率的です。

サンプルコード

#include<iostream>
using namespace std;

int higherFreq(int arr[], int n) {
    return arr[n / 2];
}

int main() {
    int arr[] = { 1, 2, 3, 4, 4, 4, 4, 4, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The number " << higherFreq(arr, n)
         << " has occurred more than or equal to "
         << n << "/2 amount of times";
}

実行結果

The number 4 has occurred more than or equal to 10/2 amount of times

補足：多数決（Boyer-Moore）アルゴリズムとの比較

この手法は「配列がソート済みであること」と「頻度n/2以上の要素が必ず存在すること」が前提条件となります。もし配列がソートされていない場合は、Boyer-Moore投票アルゴリズムなどを使用してO(n)時間で多数派要素を求める方法が有効です。一方、本記事のようにソート済み配列であれば、中央の要素を返すだけでよいため、実装も非常にシンプルになります。