Find Peak Element

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Show Tags Array Binary Search

一开始暴力搜，时间复杂度N。但迭代器没写好，参数类型不匹配。索性不写了，直接想对数解法。

对数解法，我目前知识范围内的结构只有二叉树，于是想到二分搜索。

怎么确定搜索判定条件是一个问题。首先根据我的搜索函数参数定义_findPeakElement(const vector<int> &num, int start, int end)start和end代表左闭右开区间。也即end指向的元素是不在可行解范围内的。

其次，如果mid左侧元素比mid高的话，则mid的左侧一定存在peak；如果右侧元素比mid高的话，则右侧一定存在peak。如此二分搜索。

需要注意的是，在原题中，num[-1]和num[n]被定义为无穷小，所以在边界时，只要边界元素大于邻接的那个元素就好。这里我在递归的if语句中加入了mid -1 != -1 和 mid +1 != n这两个判定。

C++代码：

class Solution {
public:
    int _findPeakElement(const vector<int> &num, int start, int end){
        //vector[end] is not included in the possible solution field.
        if(end - start == 1){
            return start;
        }
        int mid = (end + start) / 2;
        int n = num.size();
        if(mid - 1 != -1 && num[mid - 1] > num[mid]){
            return _findPeakElement(num, start, mid);
        }
        else if(mid + 1 != n && num[mid + 1] > num[mid]){
            return _findPeakElement(num, mid + 1, end);
        }
        else{
            return mid;
        }
    }
    int findPeakElement(const vector<int> &num) {
        int n = num.size();
        if(n == 0){
            return 0;
        }
        return _findPeakElement(num, 0, n);
    }
};

代码效率