You expect binary search to discard the left half. Does the code move left to the first remaining candidate, or leave it on the midpoint it already rejected? A returned answer might not reveal the difference on a friendly input. A trace makes the state changes visible.
Tracing means following a small concrete execution and recording the variables that explain each decision. You can do this by hand before coding, or instrument the program and inspect an actual run. Label the distinction: a predicted trace describes what you believe will happen; an executed trace records what did happen.
Think of following a parcel’s tracking history. “Delivered” is a final result. The sequence of locations and timestamps shows how it got there and where a delay began. A program trace gives you the corresponding sequence of states.
Choose an input that makes a decision visible
A useful trace is small enough to inspect but rich enough to exercise the branch you care about. A one-element binary search checks the singleton case. A target at the far right tests repeated rightward movement. A missing target between two values tests whether the range becomes empty correctly.
For a map-based algorithm, include a case where the successful earlier index is zero. For a graph traversal, include two paths that reach the same cell. Choose the input because it exposes a responsibility, not because it looks representative of a large data set.
Before running, write down the expected result independently. Otherwise the trace can become a convincing narrative around the wrong destination.
Fix the checkpoint
Decide whether each row records state before an iteration, after an update, or both. Mixing these conventions creates apparent contradictions that are only recording errors.
For binary search, each row can contain:
- Bounds at the start of the iteration.
- The selected midpoint and its value.
- The comparison outcome.
- Bounds after the decision, or the returned index.
You rarely need every variable. Record the smallest state that lets a reader reconstruct the decision and check the invariant.
Trace a successful search
For [1, 3, 5, 7, 9], target 9, use an inclusive interval and a loop that continues while left ≤ right.
| Step | Bounds before | Midpoint | Value | Decision | Bounds after / result |
|---|---|---|---|---|---|
| 1 |
[0, 4] |
2 | 5 | Target is larger |
[3, 4] |
| 2 |
[3, 4] |
3 | 7 | Target is larger |
[4, 4] |
| 3 |
[4, 4] |
4 | 9 | Match |
Return 4 |
The first two updates preserve every possible match and shrink the interval. The singleton interval remains eligible for inspection. Those are the design obligations you should read from the table.
The table is not a proof for every input. It is evidence about this execution and a way to inspect whether the implementation follows its stated rules.
Instrument the same algorithm
This complete function returns both the result and snapshots of its decisions:
/**
* Searches a sorted ascending array of distinct integers and records decisions.
* @param {number[]} numbers
* @param {number} target
* @returns {{
* index: number,
* steps: Array<{
* left: number,
* right: number,
* mid: number,
* value: number,
* decision: string,
* nextLeft: number,
* nextRight: number
* }>
* }}
*/
const binarySearchWithTrace = (numbers, target) => {
let left = 0
let right = numbers.length - 1
const steps = []
while (left <= right) {
const mid = left + Math.floor((right - left) / 2)
const value = numbers[mid]
const before = { left, right, mid, value }
if (value === target) {
steps.push({
...before,
decision: 'found',
nextLeft: left,
nextRight: right
})
return { index: mid, steps }
}
const decision = value < target ? 'search right' : 'search left'
if (value < target) {
left = mid + 1
} else {
right = mid - 1
}
steps.push({ ...before, decision, nextLeft: left, nextRight: right })
}
return { index: -1, steps }
}The trace stores copied numeric values at each checkpoint. If you record a mutable array or map by reference and then keep changing it, earlier trace entries may appear to change with later execution. Snapshot the relevant contents when necessary; for example, copy a map’s entries when you need its state at that moment.
Instrumentation has a cost. This search normally needs constant auxiliary space, but retaining its O(log n) trace uses additional space. Tracing every cell in a large traversal can be much more expensive, which is another reason to use a small case first.
Trace absence as carefully as presence
Now search the same array for 6:
| Step | Bounds before | Midpoint | Value | Decision | Bounds after |
|---|---|---|---|---|---|
| 1 |
[0, 4] |
2 | 5 | Target is larger |
[3, 4] |
| 2 |
[3, 4] |
3 | 7 | Target is smaller |
[3, 2] |
The range is empty, so the loop returns -1. Notice that this is a justified absence result: every discarded position was excluded by a comparison under the sorted-input guarantee. “The loop stopped” alone would not explain correctness.
An empty input produces no iteration rows and returns -1. An empty trace is not automatically a malfunction; interpret it using initialization and the loop condition.
Find the first disagreement
To compare a prediction with execution, locate the earliest checkpoint where they differ. Later states may merely inherit the initial error.
For a faulty update left = mid, searching [1, 3] for 3 can repeat bounds [0, 1] and midpoint 0 forever. The important observation is not merely “the search times out.” It is that a nonmatching iteration leaves the candidate interval unchanged. That violates progress.
For Two Sum, a trace might show that the map successfully returns index 0, followed by a branch that treats zero as false. The lookup mechanism worked; the interpretation of its result failed. That observation suggests a much narrower debugging hypothesis than “the map is broken.”
Do not rewrite the trace to match what the algorithm was supposed to do. Unexpected state is the information you came to obtain.
Know when to stop tracing
Tracing is a microscope, not a replacement for every other method. If a row reveals a violated assumption in the algorithm, return to hypothesis or pivot. If it reveals a specific implementation defect, debug. If all rows match, use the invariant to reason beyond this input and tests to cover other obligations.
Outside exercises, the same method follows state transitions in a shopping cart: request begins, response arrives, state updates, totals recompute, interface renders. Recording those stages can show whether an unexpected total originated in the response or in a later computation. A useful trace distinguishes events and state instead of printing a large object at every line.
Practice the move
Predict the rows for [1, 3, 5, 7, 9], target 1, before executing the function.
The first midpoint is index 2, so right becomes 1. The next midpoint is 0, which matches. The result is index 0. If your prediction used midpoint 1 on the second step, revisit the exact rounding rule rather than treating “somewhere in the middle” as an executable instruction.