programmingconcepts

§ 3.2 · Algorithms

Binary search

Find a value in a sorted list by checking the middle and throwing away the half it can't be in.

Binary search finds a value in a sorted list by checking the middle element and discarding the half that cannot contain the target. Each check halves what is left, so a million items need at most 20 checks: O(log n) time. It only works on sorted data, and off-by-one errors in the bounds are the classic bug.

Time
O(log n)
Extra space
O(1)
Needs
Sorted input
Requires
ArraysBig O
def binary_search(a, target):
    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
        else:
            hi = mid - 1
    return -1

Find 41 in 15 sorted values. Start with the whole array: lo = 0, hi = 14.

step 0 / 0middleruled outfound

Fig. 3.2. The blue cell is the middle being checked; grey cells are ruled out. Change the target to a value that isn't in the array, such as 40, to see how the search ends.

Intuition

Think of guessing a number between 1 and 100 when someone tells you “higher” or “lower.” The smart first guess is 50: whatever the answer, half the numbers are gone. Then 25 or 75, and so on. You never need more than 7 guesses.

Binary search plays that game on a sorted list. Each check halves the part that could still hold the target, so a million values need at most 20 checks.

How it works

  1. Keep two indexes: lo at the start and hi at the end. The target, if it’s there, is between them.
  2. Look at the middle index, mid.
  3. If a[mid] is the target, you’re done.
  4. If a[mid] is smaller, the target can only be to the right: move lo to mid + 1.
  5. If it’s larger, the target can only be to the left: move hi to mid - 1.
  6. When lo passes hi, nothing is left to check: the target isn’t there.

Complexity

Case Checks When it happens
Best 1 The target is exactly in the middle.
Worst ⌊log₂ n⌋ + 1 The target is missing, or found on the last check.

Linear search on the same list may need n checks. For n = 1,000,000 that’s a million against twenty.

Common mistakes

  1. Searching unsorted data. The halving step assumes order. On unsorted input binary search returns wrong answers without any error.
  2. Off-by-one loops. With an inclusive hi, the loop condition must be lo <= hi, and the moves must be mid + 1 and mid - 1. Mixing styles loops forever or skips values.
  3. Overflow in lo + hi. See the margin note.
  4. Sorting just to search once. Sorting costs O(n log n). For a single lookup, a linear scan is cheaper.

In other languages

Language Built-in
Python bisect.bisect_left(a, x)
JavaScript None built in
Java Arrays.binarySearch(a, x), Collections.binarySearch
C bsearch()
Go slices.BinarySearch(a, x), sort.SearchInts
Rust a.binary_search(&x)

Check yourself

Check yourself

At most how many checks does binary search need for 1,000 sorted values?

Check yourself

Can you binary search [4, 1, 9, 7] for 9?

Sources

  • Donald Knuth, The Art of Computer Programming, Vol. 3, section 6.2.1.
  • Joshua Bloch, “Extra, Extra – Read All About It: Nearly All Binary Searches and Mergesorts are Broken,” Google Research Blog, 2006.

Newsletter

One new concept each week, by email.

Signup opens soon.