75. Find Peak Element 【medium】

75. Find Peak Element 【medium】

There is an integer array which has the following features:

The numbers in adjacent positions are different.
A[0] < A[1] && A[A.length - 2] > A[A.length - 1].

We define a position P is a peek if:

A[P] > A[P-1] && A[P] > A[P+1]

Find a peak element in this array. Return the index of the peak.

Notice

It's guaranteed the array has at least one peak.
The array may contain multiple peeks, find any of them.
The array has at least 3 numbers in it.

Example

Given [1, 2, 1, 3, 4, 5, 7, 6]

Return index 1 (which is number 2) or 6 (which is number 7)

Challenge

Time complexity O(logN)

解法一：

 1 class Solution {
 2 public:
 3     /*
 4      * @param A: An integers array.
 5      * @return: return any of peek positions.
 6      */
 7     int findPeak(vector<int> &A) {
 8         if (A.empty()) {
 9             return -1;
10         }
11         
12         int start = 0;
13         int end = A.size() - 1;
14         
15         while (start + 1 < end) {
16             int mid = start + (end - start) / 2;
17             
18             if (A[mid] > A[mid - 1]) {
19                 if (A[mid] > A[mid + 1]) {
20                     return mid;
21                 }
22                 else {
23                     start = mid;
24                 }
25             }
26             else {
27                 if (A[mid] > A[mid + 1]) {
28                     end = mid;
29                 }
30                 else {
31                     start = mid;    
32                 }
33             }
34         }
35         
36         return -1;
37     }
38 };

分类讨论。

解法二：

 1 class Solution {
 2     /**
 3      * @param A: An integers array.
 4      * @return: return any of peek positions.
 5      */
 6     public int findPeak(int[] A) {
 7         // write your code here
 8         int start = 1, end = A.length-2; // 1.答案在之间，2.不会出界 
 9         while(start + 1 <  end) {
10             int mid = (start + end) / 2;
11             if(A[mid] < A[mid - 1]) {
12                 end = mid;
13             } else if(A[mid] < A[mid + 1]) {
14                 start = mid;
15             } else {
16                 end = mid;
17             }
18         }
19         if(A[start] < A[end]) {
20             return end;
21         } else { 
22             return start;
23         }
24     }
25 }

参考http://www.jiuzhang.com/solution/find-peak-element/的解法，此法更简单。