1D Peak Finder Algorithm

Question

I'm reviewing MIT Introduction to Algorithm lectures/exercises and am trying to implement a one dimensional peak finder algorithm.

I've got a working copy but it's a bit messy and I've had to put some array size constraints to get it working properly. How can I improve this implementation?

def peakfinder(arr):
 if len(arr) == 0: # If list is 0, there is no peak.
 return None
 if len(arr) == 1: # If list has been reduced to 1 element, it's a peak.
 return arr
 mid = len(arr) / 2
 left = mid - 1
 right = mid + 1
 if arr[left] <= arr[mid] >= arr[right]:
 return arr[mid] # Base case. This is a peak.
 if arr[mid] < arr[left]: # Look to left side of array for peak.
 return peakfinder(arr[:mid])
 if arr[mid] < arr[right]: # Look to right side of array for peak.
 return peakfinder(arr[mid+1:])

Answer 1

Crashing bug

If I call peakfinder([0, 0]), I get an IndexError:

Traceback (most recent call last):
 File "peaks.py", line 32, in <module>
 peakfinder([0, 0])
 File "peaks.py", line 22, in peakfinder
 if arr[left] <= arr[mid] >= arr[right]:
IndexError: list index out of range

(I’m not sure if these are the "size constraints" you allude to in the question, you didn’t provide details.)

If we inspect these, we discover that we have (L, M, R) = (0, 1, 2), but trying to get the element at index 2 will fail. This will fail whenever you have an array of length 2.

One way to handle this would be to add an extra base case for when you have an array of length 2. Alternatively, you could tweak the bounds checking so that it only looks for elements within the bounds of the array.

Let’s suppose we never pass in an array of size 2. But it turns out other arrays will hit the same, if they reduce to an length-2 array at an intermediate step. For example:

>>> peakfinder([0, 1, 0, 0])
Traceback (most recent call last):
 File "peaks.py", line 35, in <module>
 peakfinder([0, 1, 0, 0])
 File "peaks.py", line 29, in peakfinder
 return peakfinder(arr[:mid])
 File "peaks.py", line 31, in peakfinder
 if arr[mid] < arr[right]: # Look to right side of array for peak.
IndexError: list index out of range

Here’s a small test I wrote with Hypothesis to find some counterexamples:

from hypothesis import given, strategies as st
@given(st.lists(st.integers()))
def test_peakfinder_doesnt_crash(xs):
 """Finding the peak of a list doesn't crash."""
 peakfinder(xs)

The peak of an array must be an element of the array

Sounds reasonable enough, right? But your code will return a list of length 1 if any of the intermediate steps reduce to such a list, an element otherwise. For example:

>>> from peaks import peakfinder
>>> peakfinder([1, 0])
[1]
>>> [1] in [1, 0]
False
>>> peakfinder([1, 2, 3])
2
>>> 2 in [1, 2, 3]
True

You should tweak the case when len(arr) == 1 to return the single element:

if len(arr) == 1:
 return arr[0]

Here’s another small test I wrote to find a counterexample:

from hypothesis import assume, given, strategies as st
@given(st.lists(st.integers()))
def test_peak_is_in_original_list(xs):
 """The peak of a list is in the list."""
 assume(len(xs) > 0)
 assert peakfinder(xs) in xs

Answer 2

You're not checking the corners of array. Add a condition to check if mid is equal to 0 and n-1 then it shouldn't be looking in left and right side.

Answer 3

Here's a solution i was able to implement by looking at the algorithm in pseudocode more closely. It uses start and stop indexes instead of array slicing to get half the list.

def peakfinder_so(arr, i, j):
 """
 Optimized solution.
 """
 mid = (i + j) // 2
 if arr[mid - 1] <= arr[mid] >= arr[mid + 1]:
 print 'Final value: %s is bigger than %s on the left and %s on the right.' % (arr[mid], arr[mid-1], arr[mid+1])
 return mid
 elif arr[mid - 1] > arr[mid]:
 # Go left.
 return peakfinder_so(arr, i, mid - 1)
 elif arr[mid] < arr[mid + 1]:
 # Go right.
 return peakfinder_so(arr, mid + 1, j)

• Toby Speight: You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer.

Answer 4

I share my code for finding peak in a 1D array. It achieves very good performance.

def peak(a):
 n = len(a)//2
 if len(a) == 2:
 if a[0]>a[1]:
 return a[0]
 else:
 return a[1]
 if a[n-1] > a[n]:
 return peak(a[:n])
 elif a[n+1] > a[n]:
 return peak(a[n+1:])
 else:
 return a[n]

The only difference in contrast with the answers provided up to now is that I consider as a base scenario the case where the length of the array is 2. This is due to the reason that every time you check the middle element of the array with its neighbors. So if you try to do this when len(array)<=2 the index would be out of bounds.

Moreover, I always keep the part of the array with the higher neighbor so when you end up in a condition where len(array)=2 the bigger of the two elements will always be the local peak of the array.

• Mast: You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process.

Answer 5

The code should work fine once the issues mentioned by @alexwlchan are fixed, I added those changes and code looks like this:

def peakfinder(arr):
 if len(arr) == 0: # If list is 0, there is no peak.
 return None
 if len(arr) == 1: # If list has been reduced to 1 element, it's a peak.
 return arr[0]
 if len(arr) == 2:
 if arr[1]>= arr[0]:
 return arr[1]
 else:
 return arr[0]
 mid = len(arr) // 2
 left = mid - 1
 right = mid + 1
 if arr[left] <= arr[mid] >= arr[right]:
 return arr[mid] # Base case. This is a peak.
 if arr[mid] < arr[left]: # Look to left side of array for peak.
 return peakfinder(arr[:mid])
 if arr[mid] < arr[right]: # Look to right side of array for peak.
 return peakfinder(arr[mid+1:])

Now as the question mentioned how it can be improved, I went further and modified it to not use recursion to improve on time. The non-recursive code is:

 def peakfinder_norecursive(arr):
 if len(arr) == 0: # If list is 0, there is no peak.
 return None
 elif len(arr) == 1: # If list has been reduced to 1 element, it's a peak.
 return arr[0]
 else:
 left = 0
 right = len(arr)-1
 while(right-left >1):
 mid = left + (right - left)//2
 if arr[mid-1] <= arr[mid] >= arr[mid+1]:
 return arr[mid] # Base case. This is a peak.
 elif arr[mid] < arr[mid-1]: # Look to left side of array for peak.
 right = mid-1
 elif arr[mid] < arr[mid+1]: # Look to right side of array for peak.
 left = mid+1
 if arr[right]>= arr[left]:
 return arr[right]
 else:
 return arr[left]

To show the difference took a list with large n (such that last element is the peak, worst case scenario) and executed both the solutions, here are the timings-

if __name__ == "__main__":
 A = []
 for i in range(1,9999999):
 A.append(i)
 start = time.time()
 peak = peakfinder(A)
 end = time.time()
 print(end - start)
 print("Recursive Method : Peak : {}\n".format(peak))
 start = time.time()
 peak = peakfinder_norecursive(A)
 end = time.time()
 print(end - start)
 print("Non Recursive Method: Peak : {}\n".format(peak))
Output: 
0.0650475025177002
Recursive Method : Peak : 9999998
0.0
Non Recursive Method: Peak : 9999998

• Toby Speight: Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer.