binary search

← 🏠

Two approaches for binary search, iterative, and recursive.

Iterative Binary Search

 1def 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
13assert 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).

Recursive Binary Search

For some reason i find recursive algorithms easier to reason about than iterative ones. The extra space required for the call stack is an 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.

 1def 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
12print(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

$T(n) = \left\{ \begin{array}{ll} 1 & \quad n = 1 \\ T(\frac{n}{2})+1 & \quad n > 1 \end{array} \right.$

$T(n) = T(\frac{n}{2}) + 1$
$\log_2 1 = 0 n^0$
$O(log n)$