Skip to content
Tutorials Center
My learning

Topics

Lesson 73 of 225 ยท Searching

Binary Search

Learn binary search in Python: the halving idea, an invariant-based loop that avoids off-by-one bugs, the recursive version, the bisect module and step counts up to a million items.

Open a dictionary to find "mango". You do not start at page 1. You open near the middle, see that you landed on "kiwi", know that "mango" comes later, and throw away everything before that page. One more jump to the middle of what remains, and again, and in a handful of steps you are there. That is binary search: on sorted data, compare with the middle item and discard half of the remaining items every step.

The payoff is dramatic. Linear search needs up to a million comparisons for a million items. Binary search needs at most 20. Doubling the data adds only one extra step. This lesson teaches the algorithm in a way that makes the famously error-prone details (off-by-one mistakes, infinite loops) easy to get right: you will think in terms of an invariant, a statement that stays true on every iteration.

The idea

TEXT
sorted data, target = 23
index:  0   1   2   3   4   5   6   7   8   9  10
data:   2   5   8  12  16  23  38  56  72  91  99
        lo                  mid                hi     mid=5 -> 23  found!

target = 56
step 1: lo=0, hi=10, mid=5 -> 23 < 56 -> search the right half
step 2: lo=6, hi=10, mid=8 -> 72 > 56 -> search the left half
step 3: lo=6, hi=7,  mid=6 -> 38 < 56 -> search the right half
step 4: lo=7, hi=7,  mid=7 -> 56 found!

Requirement: the data must be sorted (or at least partitioned by a yes/no question, as you will see in binary search on the answer). On unsorted data the "discard half" step is simply wrong.

The invariant way to write it

Beginners often memorise a loop and then break it with lo = mid instead of lo = mid + 1. Instead, decide what you keep true. A clean choice:

Invariant: if the target is in the list, it lies in items[lo:hi+1] (the closed range lo..hi).

  • Start: lo = 0, hi = len(items) - 1 (the whole list). The invariant holds.
  • Loop while the range is not empty: lo <= hi.
  • Look at mid = (lo + hi) // 2.
    • Equal: found.
    • items[mid] < target: the target cannot be at mid or anywhere to its left, so lo = mid + 1.
    • items[mid] > target: the target cannot be at mid or to its right, so hi = mid - 1.
  • Each step shrinks the range by at least one item (we always step past mid), so the loop ends. When lo > hi the range is empty: the target is not there.
Python Iterative binary search with a trace

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why lo + (hi - lo) // 2 instead of (lo + hi) // 2? In languages with fixed-size integers (Java, C++), lo + hi can overflow for huge arrays. Python integers never overflow, so both work here, but the safe form is a good habit if you ever port the code.

How fast is it?

Each step halves the range. Starting with n items, after k steps about n / 2^k remain. The search ends when that reaches 1, so k is about log2(n). In the worst case it takes floor(log2(n)) + 1 steps.

n worst-case steps
10 4
1,000 10
1,000,000 20
1,000,000,000 30

The time is O(log n), extra space O(1) for the loop version. Python's range supports indexing and len() without storing the numbers, so we can test with a million items instantly.

Python Counting steps up to one million items

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Off-by-one traps

Binary search is the classic place for tiny mistakes. Three variants that look plausible:

Version Bug
while lo < hi with the closed range skips the case where one item remains, so a present target can be missed
lo = mid (not mid + 1) when hi = lo + 1, mid equals lo, nothing changes, infinite loop
hi = len(items) with hi = mid - 1 mixes the closed and half-open conventions; indexes out of range

Pick one convention and keep it. The closed form above uses [lo, hi]. The half-open form uses [lo, hi), starts with hi = len(items), loops while lo < hi, and moves with hi = mid and lo = mid + 1. Both are correct; mixing them is what breaks.

Python A buggy loop that never ends (stopped by a step limit)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The half-open version and the recursive version

Here are both alternatives side by side. The recursive form says the same thing with the range as parameters; its depth is only log2(n), so the recursion limit is never a problem.

Python Half-open and recursive binary search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python's bisect module

You rarely hand-write the exact search in production Python. The standard library's bisect module does the hard part:

  • bisect_left(a, x): the first index where x could be inserted keeping order (the position of the leftmost x, if present).
  • bisect_right(a, x): the index after the last x.
  • insort(a, x): insert while keeping the list sorted (the search is O(log n), the insertion shift is O(n)).

To test membership: find the index with bisect_left and check that the item there equals the target. Since Python 3.10 these functions also accept a key= function for searching records.

Python Using bisect for search, counting and insertion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Binary search beyond finding a value

The same halving idea answers many questions on sorted data, such as "where does this belong?", "first element at least x?", and "how many items are in a range?". Those are covered in binary search variants. It can also search a space of possible answers instead of a list, which is the subject of binary search on the answer.

When not to use it

  • Unsorted data. Sorting first costs O(n log n); do it only if you will search many times, otherwise use linear search.
  • Data that changes constantly. Keeping a Python list sorted costs O(n) per insertion. Consider a balanced tree or a hash table if you only need exact lookups.
  • Linked lists. You cannot reach the middle in O(1), so binary search gives no speed-up.
  • Tiny lists. For about a dozen items, a linear scan is as fast and simpler.

Common mistakes

  • Searching unsorted data and getting nonsense answers without any error.
  • Mixing closed and half-open bounds, or lo = mid loops that never end.
  • Using while lo < hi with the closed convention, missing the last candidate.
  • Forgetting duplicates: plain binary search returns some matching index, not necessarily the first. For the first or last use bisect_left / bisect_right.
  • Slicing the list in a recursive version (items[mid+1:]), which copies the data and makes the search O(n).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. About how many steps does binary search need, at most, for 1,000,000 sorted items?

    Each step halves the range, and log2(1,000,000) is about 20, so 20 steps (floor(log2 n) + 1) are enough.
  2. 2. In the closed-range version (lo..hi), what must you do when items[mid] < target?

    The target cannot be at mid or to its left. Moving lo past mid guarantees progress; lo = mid can loop forever.
  3. 3. What does bisect_left(a, x) return when x is not in the list?

    bisect_left returns an insertion point; you must check whether the item at that index equals x to know if x is present.
  4. 4. Which data cannot be searched efficiently by binary search?

    Binary search needs O(1) access to the middle item. A linked list has to be walked node by node.
  5. 5. What is the extra space of the iterative binary search?

    Only a few index variables are needed. The recursive version uses O(log n) stack space.

Summary

  • Binary search finds a value in sorted data by comparing with the middle and discarding half the range each step.
  • Time O(log n): about 20 steps for a million items. Space O(1) for the loop version, O(log n) for the recursive one.
  • Think in invariants: keep "the target, if present, is within lo..hi" true, and always move past mid.
  • Choose one convention (closed or half-open) and never mix them; lo = mid loops forever.
  • Use bisect_left and bisect_right in real code; they also handle duplicates and insertion points.
  • Requires sorted data and O(1) random access.

Next: Binary Search Variants