ピーク要素検索｜コードで実践

ピーク要素検索

このレッスンで分かること

配列の中で 両隣より大きい要素 を ピーク (peak) と呼びます

まずは素直な解法です

ただしこの問題には次の重要な性質があります

ピーク要素検索とは

両隣より大きい要素 (ピーク) の index を二分探索で O(log n) で見つけます。本レッスンでは、ピーク要素検索の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

配列の中で 両隣より大きい要素 を ピーク (peak) と呼びます。配列の端は片側だけ存在すれば ピーク 扱いです。本問題では「いずれか 1 つの ピーク の index を返す」ことを求めます。ソート されていない配列でも O(log n) で見つけられる、というのが面白いポイントです。

一見すると O(n) でしか解けなさそうな問題が、二分探索 を使うと O(log n) で解けるのは数学的に美しい例です。

線形解 (O(n))

まずは素直な解法です。for で全要素を見て、両隣との比較で判定すれば O(n) で書けます。

Python

def findPeakLinear(arr):
    n = len(arr)
    for i in range(n):
        left = arr[i-1] if i > 0 else float('-inf')
        right = arr[i+1] if i < n-1 else float('-inf')
        if arr[i] > left and arr[i] > right:
            return i
    return -1

ただしこの問題には次の重要な性質があります。配列内のどこかには必ず ピーク が存在する (条件: 隣り合う要素はすべて異なる、または端も ピーク 扱い)。

二分探索解 (O(log n))

mid を見て、mid+1 側 (右隣) の方が大きければ、右半分 に ピーク が必ず存在します (単調増加 していけばどこかでピークになる)。逆に左隣の方が大きければ 左半分 に ピーク がある。これを繰り返せば O(log n) で見つかります。

Python

def findPeak(arr):
    low, high = 0, len(arr) - 1
    while low < high:
        mid = (low + high) // 2
        if arr[mid] < arr[mid + 1]:
            low = mid + 1
        else:
            high = mid
    return low

JavaScript

function findPeak(arr) {
  let low = 0;
  let high = arr.length - 1;
  while (low < high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] < arr[mid + 1]) low = mid + 1;
    else high = mid;
  }
  return low;
}

動きの図

diagram (will load when visible)

なぜこれで正しい?

arr[mid] < arr[mid+1] のとき、右側に登っているので、右半分 のどこかで必ず 下がる (or 端に到達する) → そこが ピーク
arr[mid] >= arr[mid+1] のとき、mid 自身が ピーク 候補、または左側に ピーク がある

どちらに進んでも「ピーク を内包する半分」を残し続けるので、最後に low == high で確定する位置が ピーク。

計算量比較

解法	計算量	備考
線形	`O(n)`	実装が簡単
二分探索	`O(log n)`	`単調性` を利用
`配列内の最大値` を探す	`O(n)`	最大値は必ず `ピーク`

大規模配列 (n = 10^9 等) で O(log n) が要求されるのは、典型的な競プロ的設定です。実務でも 単調 な指標 (温度センサーの履歴 ゲームのスコア推移 等) から 局所最大 を探すケースで使えます。

よくある間違い

low <= high にしてしまい、mid + 1 が範囲外になる
arr[mid] > arr[mid+1] で >= を使ってしまう (重複を許す場合に挙動が変わる)
配列が空のときの処理を忘れる
「ピークが複数あったらどうする?」を考えすぎる (1 つ 返せば正解)

やってみよう

配列 [1, 3, 5, 4, 2] の ピーク は index=2 (5)。[1, 2, 3] の ピーク は index=2 (右端)。[5, 3, 1] の ピーク は index=0 (左端)。

端も ピーク 扱いになるルールに注意してください。単調増加 の配列なら必ず右端、単調減少 の配列なら必ず左端が答えになります。

複数の ピーク が存在する場合、テストでは「いずれかの ピーク」を期待値にしますが、本問題のテストでは一意な ピーク のみを与えるようにしているので、決め打ちで index を比較します。

よくある質問

Q. このトピックは実務でどう役立ちますか？

A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。

Q. 計算量はどう求めれば良いですか？

A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。

Q. 覚えるべき定番アルゴリズムは何ですか？

A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。

次のレッスン

次は 回転ソート配列での探索 で、ある位置で回転した昇順ソート配列から目的の値 (target) の index を O(log n) で探す方法を学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

ピーク要素の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. ピーク要素とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

ピーク要素検索