lintcode-binarysearch-find-peak-element

https://www.lintcode.com/problem/find-peak-element/description
这个题 LintCode 和 LeetCode 的 find peak element 是有区别的。 
数据上，LintCode 保证数据第一个数比第二个数小，倒数第一个数比到倒数第二个数小。 因此 start, end 的范围要取 1, A.length - 2


【思路】 --- 总结转化成一般有解一般没解的情况 若a0<a1 & an-1<an-2, a0~an-1中必含有ak, 所以判断mid处的情况，再二分。
二分法。 每次取中间元素，如果大于左右，则这就是peek。 否则取大的一边，两个都大，可以随便取一边。最终会找到peek。

正确性证明： 
1. A0 < A1 && An-2 > An-1 所以一定存在一个peek元素。 
2. 二分时，选择大的一边, 则留下的部分仍然满足1 的条件，即最两边的元素都小于相邻的元素。所以仍然必然存在peek。 
3. 二分至区间足够小，长度为3, 则中间元素就是peek。
//简洁版
class Solution {
public:
    /**
     * @param A: An integers array.
     * @return: return any of peek positions.
     */
    int findPeak(vector<int> &A) {
        // write your code here
        if(A.empty())
            return -1;
            
        int start = 1, end = A.size() - 2; //数据上，LintCode 保证数据第一个数比第二个数小，倒数第一个数比到倒数第二个数小。 因此 start, end 的范围要取 1, A.length - 2
        
        while(start + 1 < end){
            int mid = start + (end - start) / 2;
            
            if(A[mid] > A[mid + 1])
                end = mid;//注意界限的选取，每次start从第二个开始选，end 从倒数第二个开始选
            else
                start = mid + 1;//注意界限的选取，每次start从第二个开始选，end 从倒数第二个开始选 
                //--- 其实这里少+1也就是多算一种不可能的情况，也没关系，只要取范围的时候不把可能得情况漏掉即可
        }
        
        //  在最后的范围内定位。    
        if(A[start]<A[end])
            return end;
        else
            return start;
    }
};

//详细版
class Solution {
public:
    /**
     * @param A: An integers array.
     * @return: return any of peek positions.
     */
    int findPeak(vector<int> &A) {
        // write your code here
        
        if(A.empty())
            return -1;
            
        int start = 1, end = A.size() - 2;//数据上，LintCode 保证数据第一个数比第二个数小，倒数第一个数比到倒数第二个数小。 因此 start, end 的范围要取 1, A.length - 2
        while(start + 1 < end){
            int mid = start + (end - start) / 2;
 
            if(A[mid] < A [mid - 1])
                end = mid - 1;//注意界限的选取，每次start从第二个开始选，end 从倒数第二个开始选
            else if(A[mid] < A[mid + 1])//m-1<m<m+1
                start = mid + 1;
            else // m-1<m, m>m+1 --- peak
                return mid;
        }
  //  在最后的范围内定位。---这是针对导数第二个和第二个符合条件的情况，按照上面的算法找可能不能找出来        
        if(A[start] < A[end])
            return end;
        else
            return start;
        
      
    }
};