Binary search without off-by-one bugs

Searching sorted data Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

This version has a bug. What does it print?

Python 3.13
def find_last_small(vals: list[int], x: int) -> int:
    lo, hi, steps = 0, len(vals) - 1, 0
    while lo < hi and steps < 10:
        steps += 1
        mid = (lo + hi) // 2
        if vals[mid] <= x:
            lo = mid
        else:
            hi = mid - 1
    return steps

print(find_last_small([1, 2], 5))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 10

Right: with lo = mid and mid rounding down, a two-item range never shrinks; only the step cap stops it.

When one branch sets lo = mid, the middle must round up, or the search stalls on two items.

Why not the others?
  • B 1. lo stays at 0 because mid = 0 every time.
  • C 2. The range [0, 1] keeps producing mid = 0, so progress never happens.

30-second answer

Most bugs come from mixing conventions: closed ranges [lo, hi] with while lo <= hi and hi = mid - 1, versus half-open ranges [lo, hi) with while lo < hi and hi = mid. Pick one, write the invariant ('the answer is always in this range'), and check every branch keeps it true and shrinks the range. Then the loop ends with the answer at lo.

Practise saying it · 45 s. No recording, just a timer

Explain how to write a correct binary search.

Say your answer out loud, then check which of these points you covered:

  • Pick one convention
  • Write the invariant
  • Every branch must shrink the range

Deep dive

If a branch sets lo = mid, compute mid rounding up, or the loop can stall on a two-item range.

In Python, (lo + hi) // 2 never overflows; in Java and Kotlin use lo + (hi - lo) / 2 or ushr 1.

Test with 0, 1 and 2 items and with targets below, inside and above the list.

Common mistakes

  • Mixing while lo <= hi with hi = mid, which loops forever.
  • Returning mid when the loop ends instead of the agreed boundary.

Senior take & follow-ups

Say which convention you are using in one sentence before coding.

Follow-up questions

Think of your answer first, then open the hint.

  1. What is the 'first True' template?

    Show hint

    Search for the smallest i where check(i) is True: if check(mid), hi = mid, else lo = mid + 1.

  2. How do you test a binary search quickly?

    Show hint

    Compare it with a linear scan on many small random lists, as this course's harness does.

What each operation costs: Binary Search · Linear Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.