0162. 寻找峰值 #
- 标签:数组、二分查找
- 难度:中等
题目大意 #
给定一个整数数组 nums
。
要求:找到峰值元素并返回其索引。必须实现时间复杂度为 O(log n) 的算法来解决此问题。
- 峰值元素:指其值严格大于左右相邻值的元素。
注意:
- 数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。
- 可以假设
nums[-1] = nums[n] = -∞
。
解题思路 #
可以使用二分查找来查找峰值。
- 使用两个指针
left
、right
。left
指向数组第一个元素,right
指向数组最后一个元素。 - 取区间中间节点
mid
,并比较nums[mid]
和nums[mid + 1]
的值大小。- 如果
nums[mid]
小于nums[mid + 1]
,则右侧存在峰值,令left = mid + 1
。 - 如果
nums[mid]
大于等于nums[mid + 1]
,则左侧存在峰值,令right = mid
。
- 如果
- 最后,当
left == right
时,跳出循环,返回left
。
代码 #
|
|