class Solution: # @param num, a list of integer # @return an integer def findPeakElement(self, num): if len(num) <= 1: return 0 def peak(num, start, end): if end-start == 1: if start == 0 and num[start] > num[end]: return start if end == len(num)-1 and num[end] > num[start]: return end else: mid = (end+start)//2 if num[mid] > num[mid-1] and num[mid] > num[mid+1]: return mid left = peak(num, start, mid) if left != None: return left right = peak(num, mid, end) if right != None: return right return peak(num, 0, len(num)-1)
Just split the array into two halves if array[mid] is not the peak and call the findPeak function on both left and right halves recursively. Remember to include array[mid] as a part of both left and right halves.
I think your solution is still linear. Your recursion relation is
C(n) = 2 * C(n/2)
Telescope the above expression: C(n) = 2 * C(n/2) = 4 * C(n/4) = 8 * C(n/8) ... = 2^log(n) * C(1) = n * C(1)
I changed the original code so that it would only call "right = peak(num,mid,ned)" if left = park(num,start,mid) and left == None. But in this case, it's worst case runtime is still O(n) as you stated. Do you have any good idea of a logarithmic solution?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.