Binary search.

Context

Binary search halves a sorted range every step until the target is cornered. It's the textbook example of an algorithm whose efficiency is hard to feel from a complexity class. This Processing sketch makes the halving literal — a sorted strip of sixteen integers, three coloured pointers, and a tick-tock between picking a midpoint and comparing it to the target.

How it works

▸ The step machine

Each tick of the sketch toggles a single boolean — moveCur. One frame the cursor jumps to the midpoint of the active window; the next frame the value there is compared to the target and the window is shrunk on whichever side overshoots. Splitting the loop into two visible phases is the trick: the eye gets to land on the midpoint before the boundary lurches inward.

private void step() {
  if (moveCur) {
    current = start + (end - start) / 2;
  } else {
    int cur = list.get(current);
    if (cur == target) {
      return;
    }
    if (cur < target) {
      start = current + 1;
    } else {
      end = current - 1;
    }
    steps++;
  }
  moveCur = !moveCur;
}

▸ Reading the colour code

Each pointer is its own ink. Blue sits on start, orange on end, and an amber fill marks the current midpoint under inspection. The target value is shown above the strip in purple until the moment it's reached — at which point the matching cell flips to green. Anything outside the active window goes pale grey so the working set is always obvious.

▸ Driving it

The sketch auto-steps once a second from a scheduled executor, so you can drop in and watch it run unattended. Press any key to override the timer and walk through one tick at a time — useful for staring at a particular comparison.