Rounding mid Down When the Search Moves low to mid

Searching for the last true with low = mid, a range of two leaves mid on low forever, so the loop never ends; rounding mid up moves it.

A binary search that moves low to mid must round mid up, or a range of two candidates never shrinks and the loop runs for ever. The slip happens when searching for the last candidate where a predicate is true, which flips the first-true template: on a true, low moves to mid, because mid may be the answer; on a false, high moves to mid − 1. Copying the template's mid = low + (high − low) // 2 into that loop looks harmless, since it worked a moment ago. The readings 3 5 6 9 12 show the failure, searching for the last index with a reading of at most 9.

The listing runs the search both ways, with a guard that stops it after 10 rounds so the first version can print where it stuck.

rounding.pypy

readings = [3, 5, 6, 9, 12]
limit = 9


def last_at_most(round_up: bool) -> str:
    low, high = 0, len(readings) - 1
    for _ in range(10):
        if low >= high:
            return f"index {low}"
        mid = low + (high - low + (1 if round_up else 0)) // 2
        if readings[mid] <= limit:
            low = mid
        else:
            high = mid - 1
    return f"stuck after 10 rounds at low {low}, high {high}"


print("mid rounded down:", last_at_most(False))
print("mid rounded up:  ", last_at_most(True))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

mid rounded down: stuck after 10 rounds at low 3, high 4
mid rounded up:   index 3

The rounds of each version show why. Once low is 3 and high is 4, a rounded-down mid is 3 again, the reading there is 9, the predicate is true, and low moves to 3, where it already was.

text

down: low 0 mid 2 high 4, reading 6
down: low 2 mid 3 high 4, reading 9
down: low 3 mid 3 high 4, reading 9
down: low 3 mid 3 high 4, reading 9
down: ends with low 3 high 4
up: low 0 mid 2 high 4, reading 6
up: low 2 mid 3 high 4, reading 9
up: low 3 mid 4 high 4, reading 12
up: ends with low 3 high 3

Rounded up, mid in that state is 4, the reading 12 is false, and high moves to 3, ending the loop on the right answer. The rule pairs the move with the rounding: high = mid needs mid rounded down, and low = mid needs mid rounded up, low + (high − low + 1) // 2, so that mid is never the side that does not move. No error is raised; the program stops responding, and only on the inputs that reach a range of two with the predicate true at low, which a short test can easily miss.

Binary Search

← → move through sections and cards