Find Peak Element

题目:

Given an array of integers. Find a peak element in it. An array element is peak if it is NOT smaller than its neighbors. For corner elements, we need to consider only one neighbor. For example, for input array {5, 10, 20, 15}, 20 is the only peak element. For input array {10, 20, 15, 2, 23, 90, 67}, there are two peak elements: 20 and 90. Note that we need to return any one peak element.

Following corner cases give better idea about the problem.

1) If input array is sorted in strictly increasing order, the last element is always a peak element. For example, 50 is peak element in {10, 20, 30, 40, 50}.

2) If input array is sorted in strictly decreasing order, the first element is always a peak element. 100 is the peak element in {100, 80, 60, 50, 20}.

3) If all elements of input array are same, every element is a peak element.

It is clear from above examples that there is always a peak element in input array in any input array.

A simple solution is to do a linear scan of array and as soon as we find a peak element, we return it. The worst case time complexity of this method would be O(n).

这题要求我们在一个无序的数组里面找到一个peak元素，所谓peak，就是值比两边邻居大就行了。

对于这题，最简单地解法就是遍历数组，只要找到第一个元素，大于两边就可以了，复杂度为O(N)。但这题还可以通过二分来做。

解法一：简单粗暴遍历

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

解法二：二分法

首先我们找到中间节点mid，如果大于两边返回当前index就可以了，如果左边的节点比mid大，那么我们可以继续在左半区间查找，这里面一定存在一个peak，为什么这么说呢？假设此时的区间范围为[0, mid - 1]，因为num[mid - 1]一定大于num[mid]了，如果num[mid - 2] <= num[mid - 1]，那么num[mid - 1]就是一个peak。如果num[mid - 2] > num[mid - 1]，那么我们就继续在[0, mid - 2]区间查找，因为num[-1]为负无穷，所以最终我们绝对能在左半区间找到一个peak。同理右半区间一样。

 1 public int findPeak(int[] A) {
 2         // write your code here
 3         if(A.length==0) return 0;
 4         
 5         int left = 0;
 6         int right = A.length-1;
 7         int n = A.length;
 8         int mid = 0;
 9         while (left <= right)
10         {
11              mid = (left+right)/2;
12             if((mid ==0||A[mid]>=A[mid-1])&&(mid==n 1||A[mid]>=A[mid+1]))
13             {
14                 return mid;
15             }
16             
17             else if(mid>0&&A[mid-1]>A[mid])
18             {
19                 right = mid-1;
20             }
21             else 
22             {
23                 left = mid+1;
24             }
25         }
26         return mid;
27 
28     }

Reference:
http://siddontang.gitbooks.io/leetcode-solution/content/array/find_peak_element.html

http://www.geeksforgeeks.org/find-a-peak-in-a-given-array/