1. Concept library
  2. Data Structures & Algorithms
  3. Module 8: Binary search

Concept

Boundary conditions

Most binary search bugs are at the edges: an empty array, a target smaller than everything, duplicates, and the choice between lo < hi and lo <= hi. Writing the invariant down makes them go away.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

  1. Write down the invariant of a binary search before coding it
  2. Test a search on an empty array, one element and a target outside the range
  3. Spot the mix of a half-open range with a closed-range loop condition

In practice

A few lines that show Boundary conditions doing its job.

Python
def lower_bound(a, target):
    """First index whose value is >= target; len(a) if none."""
    lo, hi = 0, len(a)             # invariant: answer is in [lo, hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

lower_bound([1, 2, 2, 5], 2)    # 1
lower_bound([1, 2, 2, 5], 6)    # 4

The common mistake

Watch for

Mixing the two templates: a half-open range [lo, hi) with a lo <= hi loop, or a closed range with hi = mid. Pick one invariant and keep every line consistent with it.

What to know first

Your roadmap puts these before Boundary conditions, unless you already know them.

How it stays learned

Once a session shows you understand Boundary conditions, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

  1. Day 3First recall, while it is fresh
  2. Day 7Second, a week on
  3. Day 18Last, when it has settled
Previous in the module← Search on the answer