# My accepted O(logN) Python solution

• ``````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?

• This post is deleted!

• If you split the original into half and only do recursion in one half, the time complexity should be O(logN).

The equation is:
C(n) = C(n/2) + constant = C(n/4) + 2constant = C(8/n) + 4constant = ... = C(1) + logN * constant
Thus, O(logN) complexity

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.