0162. Find Peak Element

# 162. Find Peak Element#

## 题目 #

A peak element is an element that is greater than its neighbors.

Given an input array `nums`, where `nums[i] ≠ nums[i+1]`, find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that `nums[-1] = nums[n] = -∞`.

Example 1:

``````Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
``````

Example 2:

``````Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2,
or index number 5 where the peak element is 6.
``````

Note:

Your solution should be in logarithmic complexity.

## 题目大意 #

• 你的解法应该是 O(logN) 时间复杂度的。

## 解题思路 #

• 给出一个数组，数组里面存在多个“山峰”，(山峰的定义是，下标 `i``i-1``i+1` 位置上的元素都要大)，找到这个“山峰”，并输出其中一个山峰的下标。
• 这一题是第 852 题的伪加强版，第 852 题中只存在一个山峰，这一题存在多个山峰。但是实际上搜索的代码是一样的，因为此题只要求随便输出一个山峰的下标即可。思路同第 852 题。

## 代码 #

``````
package leetcode

// 解法一 二分
func findPeakElement(nums []int) int {
if len(nums) == 0 || len(nums) == 1 {
return 0
}
low, high := 0, len(nums)-1
for low <= high {
mid := low + (high-low)>>1
if (mid == len(nums)-1 && nums[mid-1] < nums[mid]) || (mid > 0 && nums[mid-1] < nums[mid] && (mid <= len(nums)-2 && nums[mid+1] < nums[mid])) || (mid == 0 && nums[1] < nums[0]) {
return mid
}
if mid > 0 && nums[mid-1] < nums[mid] {
low = mid + 1
}
if mid > 0 && nums[mid-1] > nums[mid] {
high = mid - 1
}
if mid == low {
low++
}
if mid == high {
high--
}
}
return -1
}

// 解法二 二分
func findPeakElement1(nums []int) int {
low, high := 0, len(nums)-1
for low < high {
mid := low + (high-low)>>1
// 如果 mid 较大，则左侧存在峰值，high = m，如果 mid + 1 较大，则右侧存在峰值，low = mid + 1
if nums[mid] > nums[mid+1] {
high = mid
} else {
low = mid + 1
}
}
return low
}

``````

Nov 25, 2022