二分查找算法只寻找峰值

我们先来看题目描述峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums找到峰值元素并返回其索引。数组可能包含多个峰值在这种情况下返回任何一个峰值所在位置即可。你可以假设 nums[-1] nums[n] -∞。你必须实现时间复杂度为 O(log n) 的算法来解决此问题。解答思路这里题目要求实现时间复杂度为 O(log n) 的算法所以很自然的想到了二分查找算法。题目中输入的数组无法保证是完全有序的不过不用担心因为题目中不要求必须找到最大的那个峰值所以我们只需要从数组的任意位置开始对局部的有序区间进行搜索即可。套用前面的二分查找模板在检查 nums[mid] 和其相邻两个元素位置之间的关系时进行如下分类如果 nums[mid-1] nums[mid] nums[mid1]则代表找到了一个峰值如果 nums[mid-1] nums[mid] nums[mid1]则代表一个上升的趋势 这时需要向右搜索如果 nums[mid-1] nums[mid] nums[mid1]则代表一个下降的趋势 这时需要向左搜索如果 nums[mid-1] nums[mid] nums[mid1]则代表找到了一个谷底此时向左或是向右搜索都可以。此外我们还需要注意一些边界条件例如 nums 中只有一个元素的情况或是 nums 中不存在峰值的情况。下面是一个动画演示的例子感兴趣的同学可以自己动手实现一下