Binary Search
Two approaches for binary search, iterative, and recursive.
Iterative Binary Search
def bin_search(A, n):
l, r = 0, len(A)-1
while l <= r:
m = (l + r) // 2
if A[m] == n:
return n
elif A[m] < n:
l = m + 1
else:
r = m - 1
return m
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).
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.
def bin_search(A, n, l=0, r=-1):
if r == -1:
r = len(A)-1
m = (l + r) // 2
if A[m] == n:
return m
if A[m] < n:
return bin_search(A, n, l=m+1, r=r)
else:
return bin_search(A, n, l=l, r=m-1)
print(bin_search([*range(20)], 10))
The recursive version has the downside of also using O(log n) space.
Related posts:
Post by Shyal Beardsley. To find out more: shyal.com.