题解 | #寻找峰值#(二分查找)

寻找峰值

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

分析: 最简单的是循环遍历O(n)

二分查找,O(log2n)

最左边和最右边为无穷小,当任意一个位置i上的值小于相邻i+1时,则左边必然存在峰值。

当任意一个位置i上的值大于相邻i+1时,右边必存在峰值。

class Solution {
public:
    // 左右边为无穷小,所以 当前位 大于临近坐标
    int findPeakElement(vector<int>& nums) {  // 索引logn 二分查找
        int len = nums.size();
        int low=0, high=len-1;
        while(low < high){
            int mid = low + high >> 1;
            nums[mid] < nums[mid+1]?low=mid+1:high=mid; 
        }
        return low;
    }
};
全部评论
题解描述有问题吧?看代码的意思是,存在某一位置nums[i] < nums[i+1]时,则继续向右查找,否则向左查找,跟“当任意一个位置i上的值小于相邻i+1时,则左边必然存在峰值。当任意一个位置i上的值大于相邻i+1时,右边必存在峰值。”描述不符。
点赞 回复 分享
发布于 2022-06-19 09:06
找到mid,如果mid<mid>mid+1,说明mid本身可能就是峰值,所以high=mid</mid>
点赞 回复 分享
发布于 2022-03-24 11:18

相关推荐

不愿透露姓名的神秘牛友
07-10 14:00
林子大了什么鸟都有啊,我觉得我说的已经很客气了,阴阳谁呢
牛客62656195...:应该不是阴阳吧?你第一次注册的时候boss就说你是牛人
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 11:20
点赞 评论 收藏
分享
评论
7
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务