Simple peak finder solution - O(log n)

I attempted a solution to a seemingly simple problem:

Peak Finder

Let input be a list. input[i] is a peak if input[i] > input[i + 1] and input[i] > input[i - 1].

Implement a recursive algorithm of time complexity $O(\log n)$ to find a peak if it exists.

def peakFinder(input):
n = len(input)
middleIndex = n/2
middleIsMax = input[middleIndex] > input[middleIndex + 1] and input[middleIndex] > input[middleIndex - 1]

# base case
if middleIsMax:
return input[middleIndex]

leftArray = input[:middleIndex]
rightArray = input[middleIndex:]

moveRight = input[middleIndex + 1] > input[middleIndex] and input[middleIndex + 1] > input[middleIndex - 1]

moveLeft = input[middleIndex - 1] > input[middleIndex] and input[middleIndex - 1] > input[middleIndex + 1]

# recursive case
if moveRight:
return peakFinder(rightArray)
elif moveLeft:
return peakFinder(leftArray)

print peakFinder([2, 41, 17, 11, 13, 7])

Are there improvements to be made? Is the time complexity $O(\log n)$?

• I think O(n) time will be needed if there can be arbitrarily large flat sections in input. – Janne Karila Jan 2 '15 at 8:21
• Consider the list x = [1] + [0] * n; random.shuffle(x). Finding the index of the 1 is equivalent to finding the peak and takes $\mathcal{O}(n)$ time. If there can't be any flats, consider x = list(range(n)); x[random.randrange(n)] += 2. Again, this is $\mathcal{O}(n)$ since it is isomorphic to the previous question. – Veedrac Jan 2 '15 at 8:44
• If I change to print peakFinder([2, 9, 17, 11, 13, 7]) I get a runtime error. I think that you are missing a base case and skipping possible solutions. – Brythan Jan 2 '15 at 8:58
• I will look into fixing my implementation. Thank you for weighing in. – ng-hacker-319 Jan 2 '15 at 9:07
• This showed up in the close queue as being broken. I feel OP should be given benefit of the doubt as it appears they didn't know it was broken. I think we can consider the case @Brythan found to be a bug/corner case. – RubberDuck Jan 2 '15 at 15:22

• Slicing a list, as in leftArray = input[:middleIndex], creates a copy and takes $O(n)$ time. You can avoid that by passing the whole list together with left and right indices as function arguments.
• Another problem with the slicing approach is that you need to look at three values to recognize the peak, but the slices can become shorter than three elements.
• Python's chained comparison would be handy here:

middleIsMax = input[middleIndex - 1] < input[middleIndex] > input[middleIndex + 1]

• the definition of this problem should include the equal case, otherwise you will have to do a linear search on this problem.

input[i] is a peak if input[i] >= input[i + 1] and input[i] >= input[i - 1].

• this method does not work for input [0, 0, 0], because there is no max, you can not moveRight or moveLeft according to your code.

• this method cannot handle null, empty array, or one item array. (I do not know much about Python, so let me know if I am wrong on this one.)

• No need to compare input[middleIndex + 1] with input[middleIndex - 1], because all you care about is if they are greater than input[middleIndex]

Edited: Here is my implementation of peak finder in Java. Hope it can help.

Implementation of peak finder