Leetcode 162: 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.

 这个题目用O（n）的时间复杂度解是很显然的，感觉题目不会这么简单，先把简单的答案做出来给面试官，然后再想办法改进，一般O（n）的复杂度有没有可能优化到O（logn)呢？ 尝试用Binary search呢？ 上次课上老师讲过用binary search 解决 unsorted array, 里面说到有时候unsorted array也是可以用binary search 来解答的， 上次的例题是unsorted array里面找single number， 很多题目如果要求O（logn)的时间复杂度，可以考虑用binary search来做。
对于unsorted array， 找二分 条件是关键。 这个题目中，如果mid 与左右两边的值存在关系，那么就可以直接返回mid，但是如果mid < mid-1 呢，那么说明在mid的左半边肯定有peak，如果mid < mid+1， 那么说明在mid的右半边肯定有peak。 
因为没有Peak的情况只有可能是数字连续上升或者连续下降，但是这两种情况下，在Mid< mid-1 或者mid < mid+1的情况下都是存在peak的。

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        //sanity check
        if (nums.size() == 0) return -1;
        if (nums.size() == 1) return 0;
        int left = 0;
        int right = nums.size()-1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (mid == 0 && mid + 1 < nums.size()) {
                if (nums[mid] > nums[mid+1]) return mid;
                left = mid + 1;
                continue;
            }
            if (mid == nums.size()-1 && mid > 0) {
                if (nums[mid] > nums[mid-1]) return mid;
                right = mid-1;
                continue;
            }
            if (nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) return mid;
            if (nums[mid] < nums[mid-1]) right = mid-1;
            else if (nums[mid] < nums[mid+1]) left = mid+1;
        }
        return -1;
    }
};