[数据结构与算法]LeetCode 162. 寻找峰值

题目链接：

力扣https://leetcode-cn.com/problems/find-peak-element/

【分析】先用个O(n)的算法试试水，直接挨个节点检测就行，但是前后边界以及n==1和n==2的特殊情况要单独拎出来检测。

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        if(n == 1) return 0;
        if(n == 2) return nums[0] > nums[1] ? 0 : 1;
        int i, j;
        for(i = 0; i < n; i++){
            if(i == 0 && nums[i] > nums[i + 1]) return i;
            else if(i == n - 1 && nums[i] > nums[i - 1]) return i;
            else if(i != 0 && i != n - 1){
                if(nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) return i;
            }
        }
        return 0;
    }
}

【二分法】因为两端都是负无穷，所以沿着一个递增的方向一定能找到一个峰值。所以可以根据当前节点和两边节点的值来决定二分的方向。

class Solution {
      public int binarySearch(int start, int end, int[] nums){
        int mid = (start + end) / 2;
        if(mid == 0){
            if(nums[mid] > nums[mid + 1]) return mid;
            else return binarySearch(mid + 1, end, nums);
        }
        if(mid == nums.length - 1){
            if(nums[mid] > nums[mid - 1]) return mid;
            else return binarySearch(start, mid - 1, nums);
        }
        if(nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) return mid;
        if(nums[mid] < nums[mid - 1]) return binarySearch(start, mid - 1, nums);
        if(nums[mid] < nums[mid + 1]) return binarySearch(mid + 1, end, nums);
        return 0;
    }

    public int findPeakElement(int[] nums) {
        if(nums.length == 1) return 0;
        return binarySearch(0, nums.length - 1, nums);
    }
}