题目
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组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 - 1- 对于所有有效的
i都有nums[i] != nums[i + 1]解法分析
使用二分查找 由于
nums[-1] = nums[n] = -∞，故沿着递增的方向必会存在峰值。然后对比相邻元素的大小，使用二分查找寻找峰值的位置即可。二分查找的写法
二分查找需要的条件
- 用于查找的内容在逻辑上来说是有序的
- 查找的数量是一个，而非多个
二分查找中区间和循环条件的确定
- 左右都闭
[left, right]- while left <= right
- left = mid + 1 ; right = mid - 1
- 左闭右开
[left, right)- while left < right
- left = mid + 1 ; right = mid
Python写法
class Solution: def findPeakElement(self, nums: List[int]) -> int: left = 0 right = len(nums)-1 m = 0 while left < right: m = (left + right) // 2 if nums[m] > nums[m+1] : right = m else : left = m + 1 return leftC语言写法
int findPeakElement(int* nums, int numsSize) { int left = 0; int right = numsSize - 1; int mid = 0 ; while(left < right) { mid = (left + right) / 2 ; if (nums[mid] > nums[mid + 1]){ right = mid; } else{ left = mid + 1; } } return left; }
