# Binary-Search Thinking - Halving the Haystack

Picture the moment. A feature that shipped fine is now broken, and you've got a range of changes to blame
- maybe a hundred commits since the last release, maybe a thousand. The instinct is to start at one end
and walk: check this change, nope; check the next, nope; the next… It feels like progress, but if the
culprit is in the middle of a thousand commits, that walk is five hundred checks of pure tedium.

Here's the secret this whole guide rests on: **you don't have to walk the range - you can halve it.**

## The idea: test the middle, throw away half

**What it actually is.** Binary search finds one item in an ordered range by always testing the *midpoint*
and using the answer to discard half of what's left. It's the same move as flipping to the middle of a
dictionary: the word's not on this page, but now you know it's in the *first* half or the *second* half -
eliminating the other half in a single look.

**Why the slow way feels right but isn't.** Walking the range one step at a time (a *linear* search) treats
every suspect as equally likely and checks them in order. Its cost grows in lockstep with the haystack:
twice as many commits means twice as many checks. Halving breaks that link entirely.

**What it does in real life.** Each test cleanly splits the remaining suspects into "before this point,
where it still worked" and "after this point, where it's broken." Keep only the half the bug must be
hiding in, find *its* midpoint, and test again. The range collapses fast:

```mermaid
flowchart LR
  s1["1000 suspects"] -->|test middle, keep broken half| s2["500"]
  s2 -->|halve| s3["250"]
  s3 -->|halve| s4["125"]
  s4 -->|halve ~6 more times| s5["1<br/>first bad commit"]
```

*What just happened:* Every test cut the suspects roughly in half, so after about ten tests a thousand
candidates collapsed to one. That "about ten" is no accident - halving a thousand ten times gets you to
one (2 to the 10th power is 1024). The shape of the win matters more than the number: **when the haystack
doubles, you pay just one more test.** Two thousand commits? About eleven. A million? About twenty. Linear
search would charge you a million.

💡 **Key point.** Linear cost grows *with* the haystack; halving cost grows with how many times you can
*double* to reach it. That gap is small for tiny ranges and enormous for big ones - which is exactly why
this feels like magic the first time a 900-commit regression falls in nine tries.

## The three things you need

Halving only works when the problem has a particular shape. Before you reach for any tool, make sure you
have all three - if one is missing, fix that first.

**1. A known-good point.** Somewhere the thing demonstrably *worked* - a commit, a release tag, a config
you trust, a date. You've seen it work or can check that it does. This is one end of your range.

**2. A known-bad point.** Somewhere it's demonstrably *broken* - usually "right now." This is the other
end. The bug was introduced *somewhere between good and bad*, and that span is your haystack.

**3. A reliable yes/no test.** At any point in between, you must be able to answer one question with
confidence: **"Is the bug present here - yes or no?"** That's the whole engine - each answer is what lets
you throw away a half. It can be clicking a broken button, running one failing test, or eyeballing an
output - but it must give the *same* answer every time you ask it at the same point.

```text
  good ●────────────────────────────────────────────● bad
   (it worked here)                          (it's broken here)
                         ▲
                   somewhere in this span, one change flipped good → bad.
                   a yes/no test at any point tells you which side it's on.
```

⚠️ **Gotcha - the test has to be trustworthy.** Every halving step *bets the whole rest of the search* on
one yes/no answer. If that answer is wrong even once - because the bug only shows up sometimes, or your
test checks the wrong thing - you'll discard the half that actually held the culprit and hunt forever in
the wrong place. A shaky test doesn't just slow a bisect down; it sends it confidently to the wrong answer.
[Phase 3](03-bisecting-beyond-git.md) comes back to this hard, since it's the single most common way
bisecting goes bad.

**Why this saves you later.** Once you can spot the "worked before / broken now" shape, you stop dreading
regressions. A scary "something in the last 300 commits broke checkout" turns into a calm, finite
procedure: nine or so tests and you have the exact change to read. The next phase hands that procedure to
a tool that picks the midpoints and does the bookkeeping for you.

## Recap

1. **Don't walk the range - halve it.** Test the midpoint and throw away the half the bug can't be in.
2. **Doubling the haystack adds one test**, not double the tests - that's why a thousand commits take
   about ten checks, not a thousand.
3. You need exactly three things: a **known-good point**, a **known-bad point**, and a **reliable yes/no
   test** for "is the bug here?"
4. The yes/no test is the engine - and it has to give the **same answer every time**, or the whole search
   goes wrong.

Watch it animated: [binary-searching for a bug](/explainers/BinarySearchDebug.dc.html)