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] &gt; input[i + 1] and input[i] &gt; 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] &gt; input[middleIndex + 1] and input[middleIndex] &gt; input[middleIndex - 1]

        # base case 
        if middleIsMax:
            return input[middleIndex]

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

        moveRight = input[middleIndex + 1] &gt; input[middleIndex] and input[middleIndex + 1] &gt; input[middleIndex - 1]

        moveLeft = input[middleIndex - 1] &gt; input[middleIndex] and input[middleIndex - 1] &gt; 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)\$?
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] &lt; input[middleIndex] &gt; input[middleIndex + 1]