title: Where is the out by one error in peak finding code?
body: <p>I am implementing the recursive algorithm for finding a peak in a 1d array <a href="https://www.geeksforgeeks.org/find-a-peak-in-a-given-array/" rel="nofollow noreferrer">finding a peak in a 1d array</a>.  My solution seems to be out by one and I am not sure why. First, here is a naive algorithm to check the answers:</p>
  
  <pre><code>def naive(A):
      n = len(A)
      if n == 1:
          return 0
      if A[0] &gt;= A[1]:
          return 0
      if A[n-1]  &gt;= A[n-2]:
          return n-1
      for i in range(1, n-1):
          if A[i] &gt;= A[i-1] and A[i] &gt;= A[i+1]:
              return i
      return -1
  </code></pre>
  
  <p>Here is my (broken) recursive solution:</p>
  
  <pre><code>def recursive(A, start, end):
      n = end - start
      if n == 1:
          return 0
      if n == 2:
          return 0 if A[start] &gt;= A[start+1] else 1
      if A[n//2] &gt;= A[n//2+1] and A[n//2] &gt;= A[n//2 - 1]:
          return n//2
      elif A[n//2 - 1] &gt;= A[n//2]:
          return recursive(A, 0, n//2)
      else:
          return n//2 + 1 + recursive(A, n//2+1, n)
  </code></pre>
  
  <p>Here is the result of testing:</p>
  
  <pre><code>n = 10
  A = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
  naive(A)
  Out[1]: 9
  recursive(A, 0, len(A))
  Out[2]: 10
  </code></pre>
  
  <p>The recursive answer is wrong.</p>
  
  <p>What have I done wrong?</p>