本文主要是介绍二分-寻找峰值，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目描述

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

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

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

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

解法思考

二分优化爬坡法

对于此问题，可以知道一个随机的下标k一定满足nums[k]>nums[k-1]&&nums[k]>nums[k+1]，于是随机的一个下标可能有两种情况：

1. nums[k]>nums[k-1] 
2. nums[k]>nums[k+1]

第一种情况下，往右边爬，可以知道在右边必有峰值；第二种情况下则是左边必有峰值。

代码

int findPeakElement(vector<int>& nums) {
        int l =0;
        int size =nums.size()-1;
        int r = size;
        int mid;
//以下两个if语句对数组的第一位和最后以为的峰值进行判断
        if(r==0) return 0;
        if(r == 1&&nums[0]>nums[1]){return 0;}
        else if(r==1&&nums[0]<nums[1]){return 1;}
        while(l<=r){
            mid = (r-l)/2+l;
//对数组的边界峰值检测
            if(mid==0&&nums[mid]>nums[mid+1]) return 0;
            else if(mid==size&&nums[mid]>nums[mid-1]) return size;
//严格符合峰值条件的数据
            if(nums[mid]>nums[mid+1]&&nums[mid]>nums[mid-1]){
                return mid;
            }
//向右取得峰值
            if(nums[mid]<nums[mid+1]){
                l = mid +1;
            }
//向左取得峰值
else{
                r = mid -1;
            }
        }
//非必要的return
        return mid;
    }

这篇关于二分-寻找峰值的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！