title: Recursive binary search not working systematically
body: <p>I am implementing the binary search algorithm with both an <strong>iterative</strong> and <strong>recursive</strong> approach.</p>
  
  <p>The first line of the input contains an integer <code>n</code> and a sequence of <code>n</code> pairwise distinct positive integers in increasing order.
  The next line contains an integer <code>k</code> and <code>k</code> positive integers.</p>
  
  <p>For all <code>i</code> from 0 to <code>k - 1</code>, output an index <code>0 &lt;= j &lt;= n-1</code> such that <code>a_j = b_i</code>, or <code>-1</code> if there is no such index. (for each algorithm implementation)</p>
  
  <p>a and b are respectively the elements of each sequence.</p>
  
  <p><strong>Input:</strong></p>
  
  <pre><code>5 1 5 8 12 13
  5 8 1 23 1 11
  </code></pre>
  
  <p><strong>Output:</strong></p>
  
  <pre><code>2 0 -1 0 -1
  2 0 -1 0 -1
  2 0 -1 0 -1
  </code></pre>
  
  <p>I managed to implement the iterative, recursive version and a linear search version.</p>
  
  <pre><code>import sys
  
  def binary_search_it(a, x):
      left, right = 0, len(a) - 1
      while left &lt;= right:
          mid = left + (right - left) // 2
          if x == a[mid]:
              return mid
          # left--mid--x--right
          if a[mid] &lt; x:
              left = mid + 1
          # left--x--mid--right
          elif x &lt; a[mid]:
              right = mid - 1
      return - 1
  
  def binary_search_rec(a, x):
      left, right = 0, len(a) - 1
      if right &lt; left:
          return left - 1
      mid = left + (right - left) // 2
      if x == a[mid]:
          return mid
      if x &lt; a[mid]:
          return binary_search_rec(a[: mid - 1], x)
      else:
          return binary_search_rec(a[mid + 1:],x)
  
  
  def linear_search(a, x):
      for i in range(len(a)):
          if a[i] == x:
              return i
      return -1
  
  if __name__ == '__main__':
      input = sys.stdin.read()
      data = list(map(int, input.split()))
      n = data[0]
      m = data[n + 1]
      a = data[1 : n + 1]
      for x in data[n + 2:]:
          # replace with the call to binary_search when implemented
          print(binary_search_it(a, x), end=' ')
      print('\n')
      for x in data[n + 2:]:
          print(linear_search(a, x), end=' ')
      print('\n')
      for x in data[n + 2:]:
          print(binary_search_rec(a, x), end = ' ')
  </code></pre>
  
  <p>So far everything is fine, for the example above the code return the same output for all three implementations.</p>
  
  <p>If I try to use another sample dataset I have an issue in my recursive approach</p>
  
  <p>Input:</p>
  
  <pre><code>5 1 2 3 4 5
  5 1 2 3 4 5
  </code></pre>
  
  <p>Output (expected):</p>
  
  <pre><code>0 1 2 3 4
  0 1 2 3 4
  0 -1 2 0 0
  </code></pre>
  
  <p>Can someone explain me the flow in my code and how you manage to identify the problem?</p>