Bisection Debugging

When a bug was introduced somewhere in a long history of commits (or a long sequence of steps, or a huge input), checking every single one one-by-one is slow. Bisection debugging — the same idea as git bisect — applies binary search (from the Algorithms course) directly to the debugging process itself: check the MIDDLE candidate, and the result tells you which half to search next.

def find_first_failing_index(results):
    lo, hi = 0, len(results)
    while lo < hi:
        mid = (lo + hi) // 2
        if results[mid]:
            lo = mid + 1   # this one passed -- bug is later
        else:
            hi = mid        # this one failed -- bug is here or earlier
    return lo if lo < len(results) else -1

This is precisely the O(log n) idea from the Complexity Analysis course, applied to debugging: 1,000 commits takes at most ~10 comparisons to bisect, not 1,000. git bisect automates exactly this loop — you tell it "good" or "bad" for whatever commit it checks out, and it narrows the search the same way.

def bisect_call_count(results):
    lo, hi = 0, len(results)
    count = 0
    while lo < hi:
        mid = (lo + hi) // 2
        count += 1
        if results[mid]:
            lo = mid + 1
        else:
            hi = mid
    return count