思路

为什么想到二分查找?

因为二分查找的本质是二段性,二分查找的过程本质是对可行区间的压缩。只要满足二段性的问题都可以用二分查找解决。在这里二段性的体现是峰值的左边单调增,右边单调减。你可能会反驳给我们的数值不只有一个峰值,但是只要我们控制好条件,一定可以把范围压缩到只有一个峰值的情况,来看看该怎么处理:

  • nums[mid] < nums[mid + 1]说明在“上坡”,则可以使left = mid + 1(因为mid肯定不是峰值),向“峰”处压缩
  • nums[mid] > nums[mid + 1]说明在“下坡”,则应该使right = mid(mid可能是峰值),往“峰”处压缩

虽然开始left和right之间可能有多个峰值,但是随着left和right不断逼近,最后两者之间一定会压缩到一个峰值上,因为两者都是向“峰”不断靠近的,但是不会超过最终的“峰”

上面分析的过程可以很轻松的使用左闭右开型二分查找实现。对左开右闭,链接左闭右开二分查找不熟的同学可以看看这篇博客【玩转二分查找Ⅰ】左闭右闭型,左开右闭型,左闭右开型(动图演绎)

代码呈现

int findPeakElement(int* nums, int numsLen ) 
{
    int left = 0;
    int right = numsLen - 1;
    while(left < right)
    {
        int mid = ((right - left) >> 1) + left; //防止直接相加发生溢出
        if(nums[mid] < nums[mid + 1])
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}