852. Peak Index in a Mountain Array
852. Peak Index in a Mountain Array
這個題目是 162. Find Peak Element 的精簡版。
- 在閉區間搜尋
- 從中間開始找
- 如果下一個數字比現在的大,向右逼近
- 如果下一個數字比現在小或是一樣,向左逼近
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
left = 0
right = len(arr) - 1
while left < right:
mid = left + (right - left) // 2
# Peak is on right hand side
if arr[mid] < arr[mid + 1]:
left = mid + 1
# Peak is on left hand side. Or mid is the peak
else: # arr[mid] >= arr[mid + 1]
right = mid
return left