JavaScriptで隣接する要素よりも大きい「ピーク要素」を検索する方法

本記事では、数値の配列を第1引数（唯一の引数）として受け取るJavaScript関数を作成します。

この関数の役割は、配列の中から「すぐ左隣の要素」と「すぐ右隣の要素」のどちらよりも大きい値（いわゆるピーク要素）を見つけて返すことです。該当する要素が複数存在する場合は、そのうちのどれか1つを返せば問題ありません。

例として、次のような入力配列が与えられた場合を考えてみましょう。

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

このとき期待される出力は次のとおりです。

const output = 9;

9は左隣の7よりも大きく、右隣の8よりも大きいため、条件を満たす要素だからです。

二分探索を応用したアプローチ

この問題は典型的な「ピーク要素の探索」であり、先頭から順に比較していく線形探索でも解けますが、二分探索（バイナリサーチ）を応用すれば、計算量をO(n)からO(log n)まで削減できます。配列がソートされていなくても適用できる点がポイントです。

具体的な手順は以下のようになります。

• まず配列内の中央付近の要素に着目します。
• その要素が前後両方の要素より大きければ、そこがピークなので現在のインデックスの値を返します。
• 右隣の要素の方が大きい場合は、右側に必ずピークが存在するため、右半分を再帰的に探索します。
• 左隣の要素の方が大きい場合は、左側に必ずピークが存在するため、左半分を再帰的に探索します。

実装コード

上記の手順を実際にコードにすると、以下のようになります。

const arr = [3, 6, 7, 9, 8, 2, 5];
const greaterThanAdjacent = (arr = [], start = 0, end = arr.length) => {
    let mid = start + Math.floor((end - start) / 2);
    let curr = arr[mid];
    let prev = mid-1 < 0 ? -Infinity : arr[mid-1];
    let next = mid+1 > arr.length-1 ? -Infinity : arr[mid+1];
    if (curr > prev && curr > next){
        return arr[mid];
    }
    if (curr < next){
        return greaterThanAdjacent(arr, mid+1, end);
    }
    if (curr > next){
        return greaterThanAdjacent(arr, start, mid-1);
    }
    return null;
};
console.log(greaterThanAdjacent(arr));

コードのポイント

この実装で注目したいのは、配列の端の処理です。midが0や配列末尾にある場合、隣接要素が存在しないため、範囲外を-Infinityとして扱っています。これにより、「先頭要素」や「末尾要素」も正しくピーク候補として評価できるようになっています。

実行結果

上記のコードを実行すると、コンソールには次のように出力されます。

9

このように、二分探索の考え方を少し変形させるだけで、ソートされていない配列からでも効率よくピーク要素を見つけることができます。大規模なデータセットを扱う際には、特に有効な手法と言えるでしょう。