二分查找

方法一遍历

由题意知，只要遍历一边得到第一个比上一个遍历数据小的数据，返回上一个数据的下标即可。

参考代码

  1. class Solution:
  2.     def peakIndexInMountainArray(self, arr: List[int]) -> int:
  3.         last = arr[0]
  4.         for n,cur in enumerate(arr):
  5.             if cur < last:
  6.                 return n - 1
  7.             last = cur

复杂度分析

时间复杂度 O(n)
空间复杂度 O(1)

方法二二分查找

二分查找。每次减半一半，判断mid对应的数据是否符合题意，即 nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]如果不满足则判断是在左边还是右边进行二分查找。

参考代码

  1. class Solution:
  2.     def peakIndexInMountainArray(self, arr: List[int]) -> int:
  3.         l,r = 0,len(arr)-1
  4.         while l <= r:
  5.             mid = l + (r - l) // 2
  6.             if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1]:
  7.                 return mid
  8.             if arr[mid] < arr[mid - 1]:
  9.                 r = mid 
  10.             else:
  11.                 l = mid

复杂度分析

时间复杂度 O(logn)
空间复杂度 O(1)