# 1-dimensional and 2-dimensional Peak Finding Algorithm

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.

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]