1-dimensional and 2-dimensional Peak Finding Algorithm
Just reviewing peak1d.


It's not clear from the docstring what kind of object array is. If it might be a list, then the complexity is actually \$O(n)\$, because slicing a list makes a copy.

The copy in array[:mid] or array[mid:] can be avoided by maintaining search bounds instead:

def peak1d(array):
    """Return a peak in array."""
    def peak(start, stop):
        mid = (start + stop) // 2
        if mid &gt; 0 and array[mid] &lt; array[mid-1]:
            return peak(start, mid)
        elif mid &lt; len(array) - 1 and array[mid] &lt; array[mid+1]:
            return peak(mid, stop)
        else:
            return array[mid]
    return peak(0, len(array))

Python doesn't do tail recursion elimination, so the function would be a bit faster if you eliminated the recursion:

def peak1d(array):
    """Return a peak in array."""
    start, stop = 0, len(array)
    while True:
        mid = (start + stop) // 2
        if mid &gt; 0 and array[mid] &lt; array[mid-1]:
            stop = mid
        elif mid &lt; len(array) - 1 and array[mid] &lt; array[mid+1]:
            start = mid
        else:
            return array[mid]