Find Peak Element

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
You may imagine that num[-1] = num[n] = -∞.
Time complexity O(logN)

https://leetcode.com/problems/find-peak-element/

Discussion

要问清楚peak是怎么定义的。O(n)的方法就太简单了，要求O(logN)的话自然就想到用二分了，这题刚开始让我困惑的是二分难道可以用在没有sort的数组上吗？？？仔细看题，"num[-1] = num[n] = -∞" 这个条件能保证了即使不是sort的数组用二分的思想就好了。

Solution

class Solution {
public:
    int findPeakElement(vector<int>& A) {
        int n = A.size();
        if(n==1) return 0;
        int start = 0; 
        int end = n-1;
        int mid;
        while (start + 1 < end) {
            mid = start + (end-start)/2;
            if((mid==0 || A[mid] > A[mid-1]) && (mid==n-1 || A[mid]>A[mid+1])) {
                return mid;
            } else if(mid>0 && A[mid] <= A[mid-1]) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (A[start] < A[end]) {
            if(end==n-1 || A[end] > A[end+1]) {
                return end;
            }
        } else if(A[start] > A[end]) {
            if(start==0 || A[start] > A[start-1]) {
                return start;
            }
        }
        return -1;
    }
};