162. Find Peak Element

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

You must write an algorithm that runs in O(log n) time.

二分搜索，由于只需要搜索任意一个山峰，因此只要向上走，一定可以走到一个峰。
当中值的下一个值是增长时（向上爬山），则更新左侧指针的位置为中值+1。继续搜索下一个中值。
否则更新右侧指针的位置为当前中值，等于向左侧进行搜索。
最后返回左侧指针停留的位置。
时间复杂度为O(logn)。

class Solution {
    public int findPeakElement(int[] num) {
        int left = 0;
        int right = num.length - 1;

        while (left < right) {
            int mid1 = (right - left) / 2 + left;
            int mid2 = mid1 + 1;
            if (num[mid1] < num[mid2])
                left = mid1+1;
            else
                right = mid1;
        }
        return left;
    }
}

一次遍历，找到峰值，返回其index。
时间复杂度为O(n)。

class Solution {
    public int findPeakElement(int[] nums) {
        int peak = 0;
        
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > nums[peak]){
                peak = i;
            }
        }
        return peak;
    }
}

分治法，每次将数组分为两组，向下递归。
当数组长度为1时返回元素，比较返回来的两个数值的大小。
返回其中的峰值index。
此解法时间为O(nlogn)。

class Solution {
    public int findPeakElement(int[] nums) {
        return findPeak(nums,0,nums.length-1);
    }
    
    private int findPeak(int[] nums, int left, int right){
        if(left == right){
            return left; 
        }
        int mid = left + (right - left) / 2;
        int i = findPeak(nums, left, mid);
        int j = findPeak(nums, mid+1, right);
        
        if(nums[i] > nums[j]){
            return i;
        }
        else{
            return j;
        }
    }
}