Binary Search

#How does it work?

Binary search finds a target in a sorted array by halving the search range at every step. It's like looking up a word in a dictionary: open somewhere in the middle and check whether your word comes before or after.

The middle element of the range is compared with the target. If they are equal, we're done. If the middle is smaller, the target is in the right half; if larger, in the left half. The other half is discarded entirely.

Because the range halves every step, even an array of a million elements needs at most 20 comparisons. The only requirement is that the data is sorted.

#Live animation

lo = 0; hi = n - 1
while lo <= hi
  mid = (lo + hi) / 2
  if a[mid] == target: return mid
  if a[mid] < target: lo = mid + 1
  else: hi = mid - 1
return -1

#Step by step

1. 01Take the whole array as the range: lo = 0, hi = n - 1.
2. 02Find the middle: mid = (lo + hi) / 2.
3. 03If a[mid] equals the target, return mid.
4. 04If a[mid] is smaller than the target, discard the left half: lo = mid + 1. If larger, discard the right half: hi = mid - 1.
5. 05Repeat until lo passes hi; an empty range means the value isn't there.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def binary_search(a: list[int], target: int) -> int:
    """a must be sorted. Returns the index of target, or -1."""
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1  # target is in the right half
        else:
            hi = mid - 1  # target is in the left half
    return -1


numbers = [1, 3, 5, 7, 9, 11]
print(binary_search(numbers, 7))
print(binary_search(numbers, 4))

#Complexity

An array of n elements shrinks to one element in at most log₂ n + 1 steps: 10 comparisons for 1,000 elements, 20 for 1,000,000. The loop version uses no extra memory; a recursive one uses O(log n) stack. Watch out: on very large arrays (lo + hi) can overflow when computing mid; lo + (hi - lo) / 2 is safer.

#When to use it?

Essential when sorted data is searched repeatedly: database indexes, dictionaries, sorted arrays (Java's Arrays.binarySearch, Python's bisect). The same idea, "binary search on the answer", solves many optimisation problems. If data changes often and can't be kept sorted, hash tables or balanced trees fit better.

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• Binary Search Tree (BST)
• Exponential Search
• Interpolation Search
• Jump Search