LeetCode 162 Find Peak Element

    
        标签：
        
            二分搜索
        
            LeetCode
        
    发布于：2022-03-04 22:59:12
    编辑于：2022-03-04 22:59:17
    浏览量：738

概述

https://leetcode.com/problems/find-peak-element/

题目要求 O(logn)

二分搜索

O(logn) 遍历肯定不行啦，排序也不行，二分吗？额，二分也得某种有序呀。

我很好奇最后的形式，是怎么 log n 的。

题目一个约束 nums[i] != nums[i + 1]，以及 nums[-1] = nums[n] = -∞ ，这个就很明显了哦。

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (true) {
            int m = (l + r) / 2;
            if ((m == 0 || nums[m] > nums[m-1]) && (m + 1 == nums.size() || nums[m] > nums[m+1])) {
                return m;
            } else if (m == 0 || nums[m] > nums[m-1]) {
                if (l == m) return r;
                l = m;
            } else {
                r = m - 1;
            }
        }
        return -1;
    }
};

Links: leetcode-162-find-peak-element