1-dimensional and 2-dimensional Peak Finding Algorithm

Question

I have the following code for a peak finding algorithm in Python 3.4.3. A peak is an element that is not smaller than its neighbors.

def peak1d(array):
 '''This function recursively finds the peak in an array
 by dividing the array into 2 repeatedly and choosning
 sides.
 Complexity: O(log n)'''
 mid = len(array)//2
 if mid > 0 and array[mid] < array[mid-1]:
 return peak1d(array[:mid])
 elif mid < len(array)-1 and array[mid] < array[mid+1]:
 return peak1d(array[mid:])
 else:
 return array[mid]
def peak2d(array):
 '''This function finds the peak in a 2D array by the
 recursive method.
 Complexity: O(n log m)'''
 n = len(array)
 m = len(array[0])
 j = m//2
 row = [i[j] for i in array]
 i = row.index(max(row))
 print(i, j)
 if j > 0 and array[i][j] < array[i][j-1]:
 return peak2d([row[:j] for row in array])
 elif j < m - 1 and array[i][j] < array[i][j+1]:
 return peak2d([row[j:] for row in array])
 else:
 return array[i][j]

I think that I could utilize the first function in 2D peak finding but I don't know if it's upto the best practices. Also, can you suggest any methods to make my program faster and better.

Just another thought, I believe it doesn't matter if we transpose the array. The peak will remain the same. So should I transpose the array to reduce the complexity at times.

Answer 1

Just reviewing peak1d.

1. 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 > 0 and array[mid] < array[mid-1]:
    return peak(start, mid)
    elif mid < len(array) - 1 and array[mid] < array[mid+1]:
    return peak(mid, stop)
    else:
    return array[mid]
    return peak(0, len(array))
   

2. 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 > 0 and array[mid] < array[mid-1]:
    stop = mid
    elif mid < len(array) - 1 and array[mid] < array[mid+1]:
    start = mid
    else:
    return array[mid]