算法-二分查找法: 162. 寻找峰值

## 问题描述
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 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]`

<h2><a class="cl-offset" name="cl-1"></a>解题思路
</h2>
根据题设条件任意两个相邻的元素比不相等
根据这一条件可以找出, 可以推断出峰顶元素必定能从左右两个区间中的某一个取得
由此实施二分查找, 可实现 `O(logn)` 的查找算法

```Go
// 寻找数组中的峰值 ( 二分查找法 )
func findPeakElement(nums []int) int {
	// 开区间 (-1, n-1)
	left, right := -1, len(nums)-1
	// 开区间不为空
	for left+1 < right {
		// 为避免溢出
		mid := left + (right-left)/2 
		// 取大值作为二次查找的区间
		if nums[mid] > nums[mid+1] { 
			right = mid
		} else {
			left = mid
		}
	}
	return right
}
```

> 引用
> [LeetCode 每日一题 162. 寻找峰值](https://leetcode.cn/problems/find-peak-element/description/?envType=study-plan-v2&envId=top-interview-150 "162. 寻找峰值")

文章目录

解题思路

清凉的茶 · i-cooltea

评论已关闭

标签

链接

其它