DAY-6 | 牛客-NC107 寻找峰值：二分法巧得峰值

一、题干

牛客网链接

NC107 寻找峰值

https://www.nowcoder.com/practice/fcf87540c4f347bcb4cf720b5b350c76

二、题解

本题也可用暴力破解：遍历数组 [1，n-1] 号位置，哪个位置的数据同时大于上一个和下一个，该数即为峰值。暴力破解法在此不多讨论，本文主要介绍一种更优的算法：二分法。

※ 二分法寻找峰值

二分法思路

通过比较左右位置与中间值的大小关系来限定寻找范围，从而确定峰值可能出现的位置。具体思路如下，注意，由于只需要找出全数组的一个峰值，因此不管是从右往左看还是从左往右看，其本质是一样的。以下我们以从右往左看的角度来分析。

首先考虑一般情况（即数组元素个数大于1，且两边边界都是非峰值点的情况）：

1. 若数组中间位置（mid）的值比它右边位置（mid + 1）的大，则认为从它最右边（right）到中间（mid）的这右半部分的数值从右向左递增的。因而，左半部分一定有一个峰值，我们要把寻找范围向左缩小，即把 right 不断向左靠拢： right = mid。

注意：不能是 right = mid-1 ，因为我们认为数组从 right 向 mid 递增，而 mid 这个位置的值也有可能就是峰值。若直接 right = mid - 1，有可能把峰值错过。

2. 当遇到 mid 位置的值比它右边（mid + 1）的小了，则可以当作数值从右向左开始递减，说明此时峰值一定在右半部分。这时将 left 向右移：left = mid + 1（将 left 移到 mid 的右边一个元素）。

注意：这里 left 不断右移的目的是确保范围右半部分数均为自右向左递增，right 不断左移的目的是确保范围左半部分数均自右向左递减。遍历到最后，范围的左界 left 不再小于右界 right 时，说明查找结束，最后留下的就是峰值。

3. 由此不断判断--移动 right 或 left 缩减范围。当范围缩至 mid+1 的位置大于等于 right 位置时，意味着这个 mid+1 位置是一个分界点：

在该位置的左半边，数值均自右往左递减；

在该位置的右半边，数值均自右往左递增。

4. 从而，此时的 mid + 1 位置，就是我们要找的峰值点。由于 left = mid + 1，因此最后返回的left值，就是峰值点所在位置。

以上为一般情况。但注意，当数组元素个数只有1个，或者首尾元素出现峰值时，这个方法就不适用了，需要特殊考虑。由于情况较少，所以并不难处理。

若数组元素个数只有一个，只需返回下标0即可；

若判断出首尾元素有峰值，则直接返回首尾元素下标即可。

代入实例，我们来看：

动态示意图

代码

int findPeakElement(int* nums, int numsLen ) { 
    //边界情况处理，1个元素前后都是负无穷 以及 0号位置大于1号位置，-1位置负无穷的情况 
    if (numsLen == 1 || nums[0] > nums[1]) 
        return 0; 
 
    //末尾位置数据大于上一个位置数据，而nums[numsLen]负无穷的情况 
    if (nums[numsLen-1] > nums[numsLen-2]) 
        return numsLen-1; 
 
    int left = 0, right = numsLen - 1, mid;
    while(left < right) { 
        mid = left + (right - left) / 2; 
        if (nums[mid] < nums[mid + 1])//中间比右边小，意味着右边肯定有个峰值
            left = mid + 1; 
        else //否则在左边包括当前位置肯定有个峰值 
            right = mid; 
    }
    return left; 
}

该算法时间复杂度为O(logN)，二分法最坏情况对整个数组连续二分，最多能分logN次。空间复杂度为O(1)，常数级变量，无额外辅助空间。