[数据结构与算法]二分法：LeetCode162 - 寻找峰值

题目：

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

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

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

You must write an algorithm that runs in O(log n) time.

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组?nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设?nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决。

思路：

这道题的朴素方法非常直接，遍历一次即可，但是二分法很难想。二分法的关键是每次舍弃掉一半的答案。那么如何才能每次判断该舍弃哪一边呢？可以这样分情况讨论：

首先判断两个边界是否符合条件，这样后面判断不会出现溢出

然后对于其中的某一位数nums[i]，如果nums[i]<nums[i+1]，那么右边一定会存在一个峰值。证明很简单，如果存在某个数开始比上一个数小，那么上一个数便是峰值；如果不存在，那么边界条件就是峰值。同理可以证明nums[i]<nums[i-1]的情况。

此时的代码复杂度为O(logn)

力扣的官方解法提供了以随机数为基础的二分法，本质是一样的。但是其中随机取数的方法值得学习。产生一个随机数利用函数rand()

int index = rand()%nums.size()

题解：

朴素方法

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int len=nums.size();
        if(len==1) return 0;
        if(nums[0]>nums[1]) return 0;
        if(nums[len-1]>nums[len-2]) return len-1;
        for(int i=1;i<nums.size()-1;i++){
            if(nums[i]>nums[i-1]&&nums[i]>nums[i+1]) return i;
        }
        return -1;
    }
};

二分法

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int len=nums.size();
        if(len==1) return 0;
        if(nums[0]>nums[1]) return 0;
        if(nums[len-1]>nums[len-2]) return len-1;

        int l=0,r=nums.size()-1,mid=0;
        while(l<=r){
            mid=(l-r)/2+r;
            cout<<"the mid is "<<mid<<endl;
            if(nums[mid]>nums[mid+1] && nums[mid]>nums[mid-1]) return mid;
            if(nums[mid]<nums[mid+1]) l=mid+1;
            else if(nums[mid]<nums[mid-1]) r=mid-1;
        }
        return -1;
    }
};