【LintCode-二分搜索】75.FindPeakElement

lintcode 75.FindPeakElement

url: https://www.lintcode.com/problem/find-peak-element/description

1、题目

Description
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 peak 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

Example 1:
Input: [1, 2, 1, 3, 4, 5, 7, 6]
Output: 1 or 6

Explanation:
return the index of peek.

Example 2:
Input: [1,2,3,4,1]
Output: 3

Challenge

Time complexity O(logN)

2、思路

经典的二分搜索

3、python代码实现

class Solution:
    """
    @param A: An integers array.
    @return: return any of peek positions.
    """

    def findPeak(self, A):
        if not A:
            return -1
        if len(A) < 3:
            return -1
        left = 0
        right = len(A) - 1
        mid = (left + right) // 2
        while left <= right:
            if left == right:
                return left
            mid = left + (right - left) // 2
            if A[mid] < A[mid + 1]:
                left = mid + 1
            else:
                right = mid


if __name__ == "__main__":
    arr = [1, 2, 1, 3, 4, 5, 7, 6]
    s = Solution()
    print(s.findPeak(arr))