162. Find Peak Element

binary search O(logn)

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        long l = 0, r = n - 1;
        while (l < r) {
            long m = l + (r - l) / 2;
            if (nums[m] > nums[m + 1]) { // 因为一定存在peak所以只要单边检查即可，之所以选择m + 1而不是m - 1是因为m一定会取到较小的那个数，也就是说m + 1一定存在，而m - 1不一定
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
};

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if ((m == 0 || nums[m - 1] < nums[m]) && (m == n - 1 || nums[m] > nums[m + 1])) {
                return m; // 循环内return一律终止条件设成l <= r
            } else if (m == 0 || nums[m - 1] < nums[m]) {
                l = m + 1; // m不可能是结果
            } else {
                r = m - 1; // m不可能是结果
            }
        }
        return -1;
    }
};

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] < nums[m + 1]) { // m never reaches n - 1
                l = m + 1;
            } else {
                r = m; // nums[m] > nums[m + 1] so m could be an answer and should be inclusive when shrinking range
            }
        }
        return l;
    }
};