Binary search is one of the more well-known algorithms, and probably the first formal algorithm someone is introduced to. I certainly had an “aha!” moment after learning how it functions and how it compares to doing a simple search via iteration.

The fundamental idea behind the algorithm is considering a sorted list of items and searching for a particular item, keep halving the list until the item is found or the the sublist is empty.

It has a worst-case time complexity of `O(lg n)`, which is generally the case with algorithms that reduce their total items in half per step. So given `n` items, binary search takes `n / 2^k` steps: `n -> n/2 -> n/4...1` I’m adding example code here in Python instead of Java because Python really lets you see how the algorithm works when a type system can be set aside. The recursive implementation:

``````def search(L, lo, hi, key):
if lo > hi: return -1

mid = (lo + hi) / 2

if L[mid] < key:
# seach left of mid
return search(L, mid + 1, hi, key)
elif L[mid] > key:
# search right of mid
return search(L, lo, mid - 1, key)
else:
return mid
``````

And the iterative implementation:

``````def search(L, lo, hi, key):
while lo <= hi:
mid = (lo + hi) / 2

if L[mid] < key:
hi = mid - 1
elif L[mid] > key:
lo = mid + 1
else:
return mid
return -1
``````