問題の定義と制約条件

隣接する要素よりも厳密に大きい値を「ピーク」と定義する。配列の両端（インデックス -1 および n）は負の無限大と見なせるため、配列内には必ず少なくとも1つのピークが存在することが数学的に保証されている。複数のピークが混在する可能性があるが、要件としていずれか1つのインデックスを返せば十分である。重要な制約として、線形探索ではなく O(log n) の対数時間計算量を持つ手法を採用する必要がある。

アルゴリズム設計の背景

配列全体が単調増加または単調減少ではないため、従来のソート済み配列向け二分探索をそのまま適用することはできない。しかし、任意の中央位置とそれより右の隣接要素を比較する操作を繰り返すことで、ピークが存在する区間を半分に絞り込める特性を利用できる。

中央要素が右隣より大きい場合、その左側（中央を含む）にピークが必ず存在する。逆に小さい場合は、右側にピークが位置する。この「傾き」の情報を利用し、探索範囲を逐次縮小していくことで、対数時間で目的のインデックスに収束させることが可能となる。

実装コード

public class PeakLocator {
    public int identifyPeak(int[] data) {
        int rangeStart = 0;
        int rangeEnd = data.length - 1;

        while (rangeStart < rangeEnd) {
            int pivot = rangeStart + (rangeEnd - rangeStart) >>> 1;
            if (data[pivot] < data[pivot + 1]) {
                rangeStart = pivot + 1;
            } else {
                rangeEnd = pivot;
            }
        }
        return rangeStart;
    }
}

計算量の解析

時間計算量

反復ごとに探索空間を正確に半分にするため、最大反復回数は配列長の対数に比例する。これにより、時間計算量は O(log N) となる。配列の長さ N が 1000 の場合でも、比較操作は 10 回程度で完了する。

空間計算量

アルゴリズムは探索範囲を示す境界変数と中央値の計算に固定数のメモリ領域しか使用しない。入力データサイズに依存しないため、空間計算量は O(1) となる。

実装における重要な考察点

• 二分探索の適用条件の変換：ソート済み配列ではなく、隣接要素の大小関係（傾き）に基づいて区間を絞り込む点が特徴。これにより単調性がないデータセットでも二分探索が有効になる。
• ループ終了条件の設計：while (rangeStart < rangeEnd) を採用し、両者が一致した時点で探索を完了する。これにより、最後の1要素が残った時点でそれが必然的にピークであると断定できる。
• オーバーフロー対策：中央値の計算に (rangeStart + rangeEnd) / 2 ではなく、差分をシフトまたは除算する方式を採用し、大規模なインデックス加算による整数オーバーフローを回避する。
• 比較対象の選択と境界更新：中央要素と右隣を比較し、右隣の方が大きい場合は探索範囲を右にシフト（rangeStart = pivot + 1）、そうでない場合は左側（中央を含む）に残す（rangeEnd = pivot）。この論理により、ピークが存在する可能性のある区間を常に維持できる。