Question: https://oj.leetcode.com/problems/find-peak-element/
Question Name: Find Peak Element
The key point is: return the index to ANY ONE of the peaks. So O(logN) is possible.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | class Solution: # @param num, a list of integer # @base, the base index for tail recursion. # @return an integer def findPeakElement(self, num, base = 0): # Refer to www.geeksforgeeks.org/find-a-peak-in-a-given-array/ # Because num[-1] = num[n] = negative infinity, if there is only # one element in the list, it is a peak. if len(num) == 1: return base # If there are two two elements in the list, the greater one is # the peak. if len(num) == 2: if num[0] > num[1]: return base else: return base + 1 mid = (len(num) - 1) // 2 if num[mid-1] < num[mid] and num[mid+1] < num[mid]: # The middle element is a peak. return mid + base elif num[mid] < num[mid-1]: # There must be one or more peak(s) in the left part. return self.findPeakElement(num[:mid], base) else: # There must be one or more peak(s) in the right part. return self.findPeakElement(num[mid+1:], mid + 1 + base) |