binary search

Go Back home

Two approaches for binary search, iterative, and recursive.

 1 def bin_search(A, n):
 2   l, r = 0, len(A)-1
 3   while l <= r:
 4     m = (l + r) // 2
 5     if A[m] == n:
 6       return n
 7     elif A[m] < n:
 8       l = m + 1
 9     else:
10       r = m - 1
11   return m
12 
13 assert bin_search([*range(20)], 10) == 10

The form here is important. We need to continue the search until the l and r pointers are equal, as breaking early could result in not finding the element being looked for.

m = (l + r) // 2 might not be OK in some languages, as you may overflow the int size. In Python, that is not a problem. l = m + 1 and r = m - 1 are also important: we already contemplated that position, hence the +- 1.

Binary search has time O(log n). It's easy to remember, as we repeatedly cut things in half until the result is found. Cutting things in half on each iteration, yields log n with log base 2. Space: O(1).

For some reason i find recursive algorithms easier to reason about than iterative ones. The extra space required for the call stack is in issue in theory, but in practice, so far nobody's asked me to re-implement a recursive algorithm into an iterative one. So i might consider adopting the recursive version of binary search as my default one.

 1 def bin_search(A, n, l=0, r=-1):
 2   if r == -1:
 3     r = len(A)-1
 4   m = (l + r) // 2
 5   if A[m] == n:
 6     return m
 7   if A[m] < n:
 8     return bin_search(A, n, l=m+1, r=r)
 9   else:
10     return bin_search(A, n, l=l, r=m-1)
11 
12 print(bin_search([*range(20)], 10))
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 6 17 18 19
graph TD 9 --> 14 9 --> 4 14 --> 17 14 --> 11 11 --> 12 11 --> 10 10 --> 10

The recursive version has the downside of also using O(log n) space.

Time Complexity



See also:

shifted array search