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

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

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

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

Note:

Your solution should be in logarithmic complexity.

思路

我们可以利用二分法来解决。

如果头尾元素是peak，返回之；不是则取头尾元素的中间值，判断其是否为peak；如果不为peak，看哪个元素大于它。从而缩小查找范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if(nums.size() == 1) return 0;
        else{
            int low = 0;
            int high = nums.size() - 1;
            int mid = (low + high) / 2;
            if(nums[low] > nums[low+1]) return low;
            else if(nums[high] > nums[high-1]) return high;
            else{
                if (mid != low && mid != high){
                    while(low < high){
                        mid = (low + high) / 2;
                        if(nums[mid] > nums[mid+1] && nums[mid] > nums[mid-1]){
                            return mid;
                        }
                        else{
                            if(nums[mid] < nums[mid-1]){
                                high = mid;
                            }
                            else if(nums[mid] < nums[mid+1]){
                                low = mid;
                            }
                        }
                    }
                    return mid;
                }
            }
        }
    }
};