难度: Medium
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
提示：
1 <= nums.length <= 1000-231 <= nums[i] <= 231 - 1i 都有 nums[i] != nums[i + 1]运行时间: 16 ms
内存: 16.0 MB
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
lo, hi = 0, len(nums)-1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < nums[mid+1]: lo = mid + 1
else: hi = mid
return lo
这个题解使用二分查找的方法来寻找峰值。由于题目要求时间复杂度为O(log n)，普通的线性扫描不符合要求。我们可以利用二分查找的思想，每次取中点，比较中点与其右侧相邻元素的大小关系，如果中点较大，说明左侧一定存在峰值，可以缩小范围到左半部分；如果中点较小，说明峰值一定在右半部分，可以缩小范围到右半部分。不断迭代直到左右边界相遇，此时找到了一个峰值。
时间复杂度: O(log n)
空间复杂度: O(1)
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
lo, hi = 0, len(nums)-1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < nums[mid+1]: # 如果中点小于其右侧相邻元素
lo = mid + 1 # 说明峰值在右半部分，缩小范围到[mid+1, hi]
else: # 如果中点大于等于其右侧相邻元素
hi = mid # 说明峰值在左半部分，缩小范围到[lo, mid]
return lo # 返回找到的峰值索引
在二分查找中，比较中点与其右侧相邻元素的原因在于简化决策过程。如果中点元素大于右侧元素，我们可以确定至少存在一个峰值在当前中点或其左侧，因为要么当前中点就是峰值，要么在中点左侧由于数组开头边界的原因存在一个递增到达峰值后递减的情况。若中点元素小于右侧元素，则至少存在一个峰值在右侧，因为从中点元素到右侧元素是递增的，必然会达到一个峰值。这样的决策保证了每次操作都能有效缩小搜索范围的一半，同时维持算法的逻辑简洁性。
题目的前提条件是nums[i] != nums[i+1]，即数组中任意相邻元素都不相等。因此，在实际的题设中，中点和其右侧元素相等的情况不会出现。这个条件简化了问题，避免了处理相等情况的复杂性，使得每次比较都可以明确决定搜索的方向，从而直接支持二分查找的决策过程。
如果中点大于其右侧的元素，这意味着从中点到中点右侧元素存在一个下坡。根据题目的设定，数组的两端可以被视为负无穷，这样在中点左侧要么存在一个上坡后下坡的峰值结构，要么中点本身就是峰值。此时，无需考虑右侧部分，因为即使右侧存在峰值，左侧的峰值更容易通过当前的二分查找路径被找到。这种判断确保了在满足中点大于右侧元素的条件下，左半部分至少存在一个峰值，从而可以安全地缩小搜索范围以加快查找速度。
在最坏情况下，二分查找每次迭代都会将搜索范围缩小到原来的一半。因此，从长度为n的数组开始，需要迭代log_2(n)次才能将搜索范围缩小到只剩一个元素，即找到峰值。这里的对数是以2为底的，因为每次操作都是将区间分为两部分。因此，这是一个典型的对数时间复杂性例子，符合题目要求的O(log n)时间复杂度。