【JavaScript】中央にピークを持つ配列のピークインデックスを二分探索で見つける方法

中央にピークを持つ配列とは

ある配列 arr が「中央にピークを持つ配列（centrally peaked array）」であるとは、以下の条件を満たすことを指します。

• arr.length >= 3

• 0 < i < arr.length - 1 を満たす添字 i が存在し、次の条件が成り立つ

  • arr[0] < arr[1] < ... arr[i-1] < arr[i]（インデックス i まで単調に増加する）

  • arr[i] > arr[i+1] > ... > arr[arr.length - 1]（インデックス i 以降は単調に減少する）

つまり、要素がまず増加していき、ある一点で最大値に達した後、再び減少していく「山型」の形状を持つ配列のことです。

問題

数値の配列 arr を第一引数（唯一の引数）として受け取るJavaScript関数を作成します。

入力される配列は必ず中央にピークを持つ配列です。この関数は、その配列におけるピーク（山頂）のインデックスを返す必要があります。

例えば、関数への入力が次のような場合を考えてみましょう。

入力

const arr = [4, 6, 8, 12, 15, 11, 7, 4, 1];

出力

const output = 4;

出力の説明

インデックス4にある要素（15）が、この配列のピーク要素だからです。

アプローチ：二分探索による効率的な解法

この問題は、線形探索でも解けますが、二分探索（バイナリサーチ）を使うことで時間計算量 O(log n) で効率的に解くことができます。

考え方はシンプルです。中央の要素とその隣接要素を比較し、以下のように判断します。

• 中央の要素が右隣より小さい場合 → ピークは右側半分に存在する

• 中央の要素が左隣より小さい場合 → ピークは左側半分に存在する

• どちらの条件にも当てはまらない場合 → 中央の要素こそがピーク

コード例

以下が実際のコードです。

const arr = [4, 6, 8, 12, 15, 11, 7, 4, 1];
const findPeak = (arr = []) => {
    if(arr.length < 3) {
        return -1
    }
    const helper = (low, high) => {
        if(low > high) {
            return -1
        }
        const middle = Math.floor((low + high) / 2)
        if(arr[middle] <= arr[middle + 1]) {
            return helper(middle + 1, high)
        }
        if(arr[middle] <= arr[middle - 1]) {
            return helper(low, middle - 1)
        }
        return middle
    }
    return helper(0, arr.length - 1)
};
console.log(findPeak(arr));

コードの解説

• まず、配列の長さが3未満の場合は条件を満たさないため -1 を返します。

• 内部のヘルパー関数 helper が再帰的に二分探索を行います。

• 範囲の中間地点 middle を計算し、隣接要素との大小関係を比較します。

• 中間の要素が両隣よりも大きければ、それがピークなのでそのインデックスを返します。

出力

4

このように、二分探索を利用することで、大規模な配列に対しても高速にピークのインデックスを求めることができます。