162. 寻找峰值

题意：

解题思路：

思路：(二分) O(logn)
* 如果 nums[i-1] < nums[i]，则如果 nums[i-1], nums[i], ... nums[n-1] 是单调的，则 nums[n-1]就是峰值；
* 如果nums[i-1], nums[i], ... nums[n-1]不是单调的，则从 i 开始，第一个满足 nums[i] > nums[i+1]的 i 就是峰值；所以 [i,n−1] 中一定包含一个峰值；
* 如果 nums[i-1] > nums[i]，同理可得 [0,i−1] 中一定包含一个峰值；
* 每次二分中点，判断nums[i-1]和nums[i]的大小关系来确定左右两边哪边有峰值，从而来缩小一半的检索区间；

PHP代码实现：

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function findPeakElement($nums) {
        $l = 0;
        $r = count($nums) - 1;
        while ($l < $r) {
            $m = $l + floor(($r - $l) >> 1);
            if ($nums[$m] > $nums[$m + 1]) {
                $r = $m;
            } else {
                $l = $m + 1;
            }
        }
        return $l;
    }
    function findPeakElementOn($nums) {
        $n = count($nums) - 1;
        for ($i = 1; $i <= $n; $i++) {
            if ($nums[$i] < $nums[$i - 1]) return $i - 1;
        }
        return $n;
    }
}

GO代码实现：

func findPeakElement(nums []int) int {
    l, r := 0, len(nums) - 1
    for l < r {
        m := l + (r - l) >> 1
        if nums[m] > nums[m + 1] {
            r = m
        } else {
            l = m + 1
        }
    }
    return l
}

C++代码实现：

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