Pythonで配列のピーク要素を見つける方法|二分探索による効率的な実装

配列の中からピーク要素(peak element)を探す問題について解説します。ピーク要素とは、両隣の要素よりも大きい要素のことです。入力配列 nums では nums[i] ≠ nums[i+1] が常に成り立つものとし、ピーク要素を1つ見つけてそのインデックスを返します。配列に複数のピーク要素が含まれる場合は、そのうちどれか1つのインデックスを返せば構いません。さらに、配列の範囲外は nums[-1] = nums[n] = −∞ とみなせるため、端の要素もピークになり得ます。

例えば、配列が [1, 2, 1, 3, 5, 6, 4] の場合、ピーク要素はインデックス 1(値 2)と インデックス 5(値 6)の2箇所に存在します。

アルゴリズムの流れ

この問題は二分探索(binary search)を応用することで、O(log n) の時間計算量で解けます。手順は以下の通りです。

• low := 0、high := 配列の最終インデックス で初期化する
• low < high の間、次の処理を繰り返す
  • mid := low + (high − low + 1) // 2 を求める
  • mid − 1 ≥ 0 かつ nums[mid − 1] ≤ nums[mid](右方向に登り坂がある)なら low := mid、そうでなければ high := mid − 1 とする
• ループを抜けたときの low がピーク要素のインデックスなので、それを返す

実装例(Python)

class Solution(object):
    def findPeakElement(self, nums):
        low = 0
        high = len(nums) - 1
        while low < high:
            mid = low + (high - low + 1) // 2
            if mid - 1 >= 0 and nums[mid - 1] <= nums[mid]:
                low = mid
            else:
                high = mid - 1
        return low

ob1 = Solution()
print(ob1.findPeakElement([15, 35, 85, 96, 5, 6, 8, 12]))

入力

[15, 35, 85, 96, 5, 6, 8, 12]

出力

3

なぜ二分探索が有効なのか

配列はソートされていませんが、「配列の外側は −∞」という条件のおかげで、必ず少なくとも1つのピークが存在することが保証されています。mid の位置で nums[mid − 1] ≤ nums[mid]、つまり右方向に値が増えているなら、その先に必ずピークが存在するため、探索範囲を右側に狭められます。逆に右方向が下り坂なら、ピークは左側にあることが分かります。この判断を繰り返すことで毎回探索範囲が半分になり、時間計算量は O(log n)、追加メモリも不要で空間計算量は O(1) に抑えられます。