Two approaches for binary search, iterative, and recursive.
Iterative Binary Search
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
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
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:
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 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))
The recursive version has the downside of also using
O(log n) space.
shifted array search