共计 1510 个字符，预计需要花费 4 分钟才能阅读完成。
题目 ：
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能蕴含多个峰值，在这种状况下，返回 任何一个峰值 所在位置即可。
你能够假如 nums[-1] = nums[n] = -∞。
你必须实现 工夫复杂度为 O(log n) 的算法来解决此问题。
链接：力扣 Leetcode—中级算法—排序和搜寻—寻找峰值.
示例 1:
输出：nums = [1,2,3,1]
输入：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输出：nums = [1,2,1,3,5,6,4]
输入：1 或 5
解释：你的函数能够返回索引 1，其峰值元素为 2；
或者返回索引 5，其峰值元素为 6。
标签：数组、二分查找
思路 ：本题首先最容易想到的就是遍历数组，找出第一个符合条件的元素就能够了，这很简略，然而不满足 O(logN) 的工夫复杂度要求
那么咱们想要满足 O(logN)的工夫复杂度要求，那么必定就是采纳二分法
二分法：
- 定义高下两个指针 low，high，别离指向数组首位
- 定义两头指针 mid=(low+high)/ 2 咱们晓得二分法的完结标记是 low>=high，当 low==high 的时候，算法必定完结
- 而后咱们每次判断两头值，如果两头值处于降落状态，那么能够必定两头值的右边有比两头值大的数，而数组中间又是十分小的数，所以峰值必定在右边，所以咱们二分法的下一次开始就是让 high=mid
- 如果两头值处于回升状态，那么峰值必定就在两头值的左边，所以二分法的下一次开始就是让 low=mid+1
- 你须要认真感触 high=mid 和 low=mid+ 1 这两个等式，琢磨轻微之处，能够发现 low 随着 mid 挪动，而 high 最多等于 mid，认真琢磨他们的区别
全副 Go 代码如下：
package main
import "fmt"
// 二分法
func findPeakElement(nums []int) int {low, high := 0, len(nums)-1
for low < high {mid := (low + high) / 2
if nums[mid] > nums[mid+1] {high = mid} else {low = mid + 1}
}
return low
}
func main() {a := []int{1, 2, 3, 1}
fmt.Println(findPeakElement(a))
}
提交截图：
这里我也写一下遍历：
全副 Go 代码如下：
package main
import "fmt"
// 遍历
func findPeakElement(nums []int) int {
var max int
n := len(nums)
// 数组长度为 1，那第一个就是最大，地位为 0
if n == 1 {max = 0} else if n == 2 {
// 数组长度为 2，比拟一下，如果第 2 个大于第 1 个，地位 1 为最大，其余都是地位 0 最大
if nums[1] > nums[0] {max = 1} else {max = 0}
} else if n > 2 {
// 数组长度大于 2，遍历数组，如果有大于右边并且大于左边的，记下地位并且跳出遍历
for i := 1; i < n-1; i++ {if nums[i-1] < nums[i] && nums[i] > nums[i+1] {
max = i
break
} else if nums[1] < nums[0] {
// 如果没有合乎下面的要求，就剩下始终增的数组或者始终减的数组两种状况，只须要比拟第一和第二个数
max = 0
// 第一个数大，那地位 0 就是最大的
} else if nums[1] > nums[0] {
max = n - 1
// 第二个数大，那地位 n - 1 就是最大的
}
}
}
return max
}
func main() {a := []int{1, 2, 3, 1}
fmt.Println(findPeakElement(a))
}
提交截图：
正文完
