Find Peak Element*

There is an integer array which has the following features:

The numbers in adjacent positions are different.

A[0] < A[1] && A[A.length - 2] > A[A.length - 1].

We define a position P is a peek if:

A[P] > A[P-1] && A[P] > A[P+1]

Find a peak element in this array. Return the index of the peak.

Example

Given [1, 2, 1, 3, 4, 5, 7, 6]

Return index 1 (which is number 2) or 6 (which is number 7)

Solution

题目不容易理解，就是求一个值大于左右两边即是峰值，返回值是索引即可。二分法的精髓就是中点最重要，可以用开始，结束去比较，也可以直接中点跟中点自己玩，变形题目.

class Solution:
    #@param A: An integers list.
    #@return: return any of peek positions.
    def findPeak(self, num):
        if len(num) == 0 :
            return -1
        start , end = 0, len(num) - 1 #有可能数组里面只有两个元素。
        while start + 1 < end:
            mid = ( start + end ) / 2
            if num[mid] < num[mid - 1]:
                end = mid
            elif num[mid] < num[mid + 1]:
                start = mid
            else:
                end = mid
        if num[start] < num[end]:
            return end
        else:
            return start