162. Find Peak Element

162. Find Peak Element

這個題目存在著一個滿容易的解法，因為題目只要找到任意一個峰值即可，所以可以用比較直覺的方式不斷的往上爬，找到第一個下降點即可，這樣的時間複雜度會在線性的時間複雜度，其實並不算差。

但是這個題目困難是存在一個二分搜索的解法，其時間複雜度可以在對數時間複雜度找到答案。

二分搜尋的邏輯如下，每次從中間位置的值開始檢查

1. 如果中間位置下一個位置的值，比當前位置的值大，代表頂峰位於右側區間，且不包含當前的位置。（繼續爬山的概念）所以可以把左側的指針移動到當前位置的下一個位置。
2. 如果中間位置下一個位置的值，和當前為值的值一樣大，或是更小，代表現在我們可能再往下山的位置，又或是已經在頂峰了，頂峰的位置一定是在左側區間，又或是在當前的位置。所以可以把右側的指針移動到當前位置。

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                right = mid
        return left