pylist

75. Find Peak Element

There is an integer array which has the following features:

We define a position P is a peak if:

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

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)

Solution

class Solution:
    """
    @param A: An integers array.
    @return: return any of peek positions.
    """
    def findPeak(self, A):
        # corner cases
        
        # bisection init
        # from the first to the second last
        up = len(A) - 2
        low = 0
        while(low + 1 < up):
            mid = int((up - low)/2) + low
            if A[mid] < A[mid + 1]:
                # same as A[0] < A[1]
                low = mid
            if A[mid] > A[mid + 1]:
                # same as A[A.length - 2] > A[A.length - 1].
                up = mid
            # if A[mid] == A[mid + 1]:
                # The numbers in adjacent positions are different.
        # because $low$ might be 0, so check $up$ first
        if A[up] > A[up - 1] and A[up] > A[up + 1]:
            #  Return the index of the peak.
            return up
        else:
            return low

questions to ask

Special care: