寻找峰值

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int findPeakElement (int[] nums) {
        // write code here
        int left = 0;
        int right = nums.length -1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[mid + 1]){
                right = mid ;
            }else{
                left = mid + 1;
            }
        }
        return right;
    }
}

采用分治的思想，两侧都会进行查找

1. 如果区间元素数量大于1，则进行分治

2. 如果区间元素数量等于1，进行判断

   public class Solution {
    public int findPeakElement (int[] nums) {
        return findPeek(nums, 0, nums.length - 1);
    }
   
    public int findPeek(int[] nums, int l, int r) {
        if (l == r) {  // 区间只有一个元素时进行判断
            if (nums.length == 1) {  // 数组本来就一个元素，则一定是峰值 
                return l;
            } else {  // 数组大于一个元素
                if (l > 0 && l < nums.length - 1) {  // 该元素位于中间
                    if (nums[l] > nums[l - 1] && nums[l] > nums[l + 1]) {
                        return l;
                    }
                } else if (l == 0) {  // 该元素位于左侧
                    if (nums[l] > nums[l + 1]) {  
                        return l;
                    }
                } else if (r == nums.length - 1) {  // 该元素位于右侧
                    if (nums[r] > nums[r - 1]) {
                        return r;
                    }
                }
            }
        } else {  // 区间大于一个元素时分治
            int mid = (l + r) >> 1;
            int lres = findPeek(nums, l, mid);  // 找左侧的峰值
            int rres = findPeek(nums, mid + 1, r);  // 找右侧的峰值
            if (lres != -1) return lres;
            if (rres != -1) return rres;
        }
   
        return -1; // 找不到峰值返回-1
    }
   }

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int findPeakElement (int[] nums) {
        // write code here
        int min = 0,
            max = nums.length - 1;
        
        while(max - min > 1) {  // not adjacent
            int mid = (min + max) / 2;
                        
            if (nums[mid] > nums[mid + 1]) {    // larger than right, go left
                max = mid;
            } else {    // larger than left, go right
                min = mid;
            }
        }

        return nums[min] > nums[max] ? min : max;

                // 别的答案总是在某一个条件下+1，看不懂为什么
                // 不如得到答案所在的相邻两个结果，选符合条件的那个
                // 二分搜索应该具有对称美
    }
}

暴力求解完事
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int findPeakElement (int[] nums) {
        // write code here
        if(nums.length == 2)
            if(nums[0] > nums[1])
                return 0;
            else return 1;    
        for(int i = 1; i < nums.length-1; i++){
            if(nums[i] > nums[i+1] && nums[i] > nums[i-1])
            return i;
            if(nums[i]< nums[i+1] && i == nums.length-2)
            return i+1;
        }
        return 0;
    }
}

public int findPeakElement (int[] nums) {
        //二分查找
        //局部峰值  左小  中大  右小
        //返回一个峰值就可以
        //一直往高处走，找一个标杆元素（区间中点）把数组分为两个区间，每次向较高的一边走
        //二分查找，从收尾开始每次取中间值，直到首尾相遇
        //区间收尾相遇的点，就是波峰
        int left=0;
        int right=nums.length-1;
        while(left<right){//当left==right，返回的就是ans
            int mid=(left+right)/2;
            if(nums[mid]>nums[mid+1]){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return right;

    }

public int findPeakElement (int[] nums) {
    // write code here
    int p1=0 ,p2=nums.length-1;
    while(p1<p2){
        int mid=(p1+p2)/2;
        // 考虑奇偶数，一定会存在mid和mid+1
        if(nums[mid]<=nums[p2]){
            p1=mid+1;
        }else{
            p2=mid;
        }
    }
    return p1;
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int findPeakElement (int[] nums) {

        int num = Integer.MIN_VALUE;
        int index = -1;
        for (int i = 0; i < nums.length; i++) {
            if (num < nums[i]) {
                num = nums[i];
                index = i;
            }
        }
        return index;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int findPeakElement (int[] nums) {
        // write code here
        int length = nums.length;
        if (nums == null || length == 0) {
            return -1;
        }
        if (length == 1) {
            return 0;
        }
        //时间复杂度为 O(n)
       // for (int i = 0; i < length; i++) {
     //       if (nums[i] > get(i - 1, length, nums) && nums[i] > get(i + 1, length, nums)) {
     //           return i;
     //       }
     //    }
     //    return -1;
        return doFindPeakElement(nums);
    }

    private int doFindPeakElement(int[] nums) {
        int length = nums.length;
        int start = 0;
        int end = length - 1;
        while (start <= end) {
            int mid = (end - start) / 2 + start;
            int left = get(mid-1, length, nums);
            int right = get(mid+1, length, nums);
            if(nums[mid] > left && nums[mid] > right) {
                return mid;
            } else if (nums[mid] <= left) {
                end = mid-1;
            }else {
                start = mid+1;
            }
        }
        return -1;
    }

    private int get(int i, int length, int[] nums) {
        int min = Integer.MIN_VALUE;
        if (i >= length) {
            return min;
        }
        if (i < 0) {
            return min;
        }
        return nums[i];
    }

}

//思路
//O(lgn)
1、利用二分查找算法思想，首先从中间位置开始查找
2、判断中间值比左边和右边值都大则中间值为峰值，否则进行第3步
3、判断中间值小于等于左边值则峰值在左边侧 则 end = mid-1
4、判断中间值大于等于右边值则峰值在右侧 则 start = mid+1