ソート済み配列から25%超出現する要素をJavaScriptで効率的に見つける方法

問題概要

本記事では、昇順にソートされた整数配列を受け取り、全体の4分の1（25%）を超える回数出現している整数を返すJavaScript関数を実装します。

このような特別な出現頻度を持つ要素は、配列内にちょうど1つだけ存在することが保証されているため、工夫された探索戦略によって高速に答えを導き出せます。

入力例と出力例

たとえば、関数に次の配列を渡した場合を考えてみましょう。

const arr = [3, 5, 5, 7, 7, 7, 7, 8, 9];

期待される出力は以下の通りです。

const output = 7;

配列の長さは9なので、その4分の1は2.25です。7は合計4回出現しており、2.25を上回るため、これが求める要素となります。

アプローチのポイント：二分探索との組み合わせ

配列がソート済みであることを活かせば、全要素を線形に数え上げるよりも効率的な解法が可能です。ここで重要なのは、「25%を超えて出現する要素は、必ず配列の長さの 1/4、2/4、3/4 のいずれかのインデックス位置にまたがって現れる」という性質です。

したがって、この3つの候補位置に注目し、それぞれの値について二分探索で最左の出現位置と最右の出現位置を特定すれば、出現回数を高速に計算できます。

実装コード

const arr = [3, 5, 5, 7, 7, 7, 7, 8, 9];
const oneFourthElement = (arr = []) => {
    const len = arr.length / 4;
    const search = (left, right, target, direction = 'left') => {
        let index = -1;
        while (left <= right) {
            const middle = Math.floor(left + (right - left) / 2);
            if (arr[middle] === target) {
                index = middle;
                if (direction === 'left') {
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            } else if (arr[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return index;
    };
    for (let i = 1; i <= 3; i++) {
        const index = Math.floor(len * i);
        const num = arr[index];
        const loIndex = search(0, index, num, 'left');
        const hiIndex = search(index, arr.length - 1, num, 'right');
        if (hiIndex - loIndex + 1 > len) {
            return num;
        }
    }
};
console.log(oneFourthElement(arr));

コンソール出力

7

コードの解説

• 閾値の計算：arr.length / 4 を基準値 len として保持します。出現回数がこの値を厳密に超えれば、条件を満たすことになります。
• search 関数：標準的な二分探索を拡張したものです。direction 引数によって「ターゲットの最左インデックス」または「最右インデックス」を切り替えて返せるようにしており、値が見つかった後も探索を続行することで両端を特定します。
• 候補の走査：i = 1 から 3 までループし、配列長の i/4 に相当する位置にある値を取得します。左右それぞれの境界インデックスを二分探索で求め、hiIndex - loIndex + 1（= 出現回数）が len を超えていれば、その時点で該当する値を返します。

計算量

チェックする候補位置はわずか3つで、各候補につき2回の二分探索を実行するため、全体の時間計算量は O(log n) に収まります。全要素を走査する O(n) の素朴な解法と比べ、大規模な配列ほど有利になるアプローチです。また、追加の記憶領域をほとんど必要としないため、空間計算量も O(1) と非常に効率的です。