1D Peak Finder Algorithm 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] &lt;= arr[mid] &gt;= arr[right]:
        return arr[mid] # Base case. This is a peak.

    if arr[mid] &lt; arr[left]: # Look to left side of array for peak.
        return peakfinder(arr[:mid])

    if arr[mid] &lt; arr[right]: # Look to right side of array for peak.
        return peakfinder(arr[mid+1:])
Crashing bug

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

Traceback (most recent call last):
  File "peaks.py", line 32, in &lt;module&gt;
    peakfinder([0, 0])
  File "peaks.py", line 22, in peakfinder
    if arr[left] &lt;= arr[mid] &gt;= 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&nbsp;2.

One way to handle this would be to add an extra base case for when you have an array of length&nbsp;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:

&gt;&gt;&gt; peakfinder([0, 1, 0, 0])
Traceback (most recent call last):
  File "peaks.py", line 35, in &lt;module&gt;
    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] &lt; 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&nbsp;1 if any of the intermediate steps reduce to such a list, an element otherwise. For example:

&gt;&gt;&gt; from peaks import peakfinder
&gt;&gt;&gt; peakfinder([1, 0])
[1]
&gt;&gt;&gt; [1] in [1, 0]
False
&gt;&gt;&gt; peakfinder([1, 2, 3])
2
&gt;&gt;&gt; 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) &gt; 0)
    assert peakfinder(xs) in xs