Testing and Validation Strategies
Debugging by bisection cuts debugging time from linear to logarithmic by eliminating half the search space with each checkpoint check.
The Cost of Checking Everything
When a large program first produces an incorrect result, a natural response is to inspect each line in order. This is a linear search: the possible bug locations are reduced one line at a time. In a 100-line program, the worst case could require checking all 100 lines. That approach works, but it treats every line as a separate destination instead of using the information already available from the program's intermediate behavior.
| Program size | Linear search | Bisection |
|---|---|---|
| 100 lines | Up to 100 checks | About 7 checks |
| 1000 lines | Up to 1000 checks | About 10 checks |
The source compares checking every line with repeatedly halving the remaining search space.
Halving the Search Space
Bisection changes the question from “Which line is wrong?” to “Which half of the remaining code contains the transition from correct behavior to incorrect behavior?” Place a checkpoint at an intermediate point and inspect the value or state produced there. If that checkpoint is correct, the bug is in the later region. If it is incorrect, the bug is in the earlier region. You then repeat the same reasoning inside the remaining region.
The boundary is the point between the last correct intermediate value and the first incorrect intermediate value. Bisection is a strategy for locating that boundary by repeatedly dividing the suspect region.
Checkpoint Placement in Loops
In theory, bisection means checking the exact middle of the code. In a real loop, the exact middle line may not provide a useful value to inspect. A loop may have no convenient verification point at that location. Instead, choose a checkpoint that follows the program's logical flow and produces a state you can verify.
- Check after the loop completes if the loop's final result is easy to verify.
- Check at the end of an iteration when each iteration produces a meaningful intermediate state.
- Check after a key calculation when that calculation separates two logical regions of the process.
- Partition the remaining problem into two regions that are approximately equally likely to contain the bug, based on your understanding of the code.
A Bisection Walkthrough
Finding a Faulty Region in 100 Lines
A 100-line program produces an incorrect final result. Use bisection to narrow the likely location of the bug.
- 1First check
Inspect an intermediate value around the middle of the logical process. The original 100 possible lines are divided into two regions of about 50 lines.
- 2Second check
Keep the half that contains the transition from correct behavior to incorrect behavior. That region now contains about 25 possible lines.
- 3Third check
Check an intermediate value in the remaining region. The search is reduced to about 12 or 13 lines.
- 4Later checks
Continue dividing the remaining region. After four checks, about 6 or 7 lines remain; after five, about 3 or 4 remain; after six, about 1 or 2 remain.
- 5Final inspection
Compare the last correct checkpoint with the first incorrect checkpoint. The faulty code is isolated to the small region between them.
A 100-line search that could require up to 100 linear checks can be narrowed to about 7 bisection checks.
The walkthrough does not require the checkpoint to be a literal line number. In a loop, the checkpoint might be the state after a particular iteration or after a key calculation. What matters is that the check separates a region known to behave correctly from a region that may contain the fault.
Estimating the Checks
To estimate the effort, track how many possible locations remain after each check. Bisection reduces the search from 100 to about 50, then 25, then 12 or 13, then 6 or 7, then 3 or 4, and finally 1 or 2. The exact count can vary because a program cannot always be divided into perfectly equal regions, but the important pattern is repeated halving. This is why the source describes the method as logarithmic rather than linear.
| Possible locations | Approximate bisection checks |
|---|---|
| 100 lines | About 7 |
| 1000 lines | About 10 |
These are the source's approximate worst-case comparisons for bisection.
A program has about 1000 possible lines where an error might be located. Compare the effort of checking lines one by one with the effort of bisection.
Hints
- For a linear search, use the number of possible lines.
- For bisection, use the source's approximate estimate for a 1000-line program.
Common Debugging Mistakes
Common mistake Checking every line automatically
What it looks likeBeginning at the first line and inspecting each line in sequence in a large program.
Why it failsThis creates a linear search and can require up to 100 checks for a 100-line program.
Do this insteadUse an intermediate checkpoint to decide which half of the remaining code deserves attention.
Common mistake Treating the exact middle line as mandatory
What it looks likeTrying to place a check at line 50 simply because a program has 100 lines.
Why it failsThe exact middle may not produce a useful value and may not match the program's logical structure.
Do this insteadChoose a checkpoint after a meaningful calculation, iteration, or result that can be verified.
Common mistake Checking a state that cannot be interpreted
What it looks likeInspecting a complex data structure at an arbitrary point without knowing what a correct state should look like.
Why it failsA checkpoint cannot reliably divide the search if its value is difficult to verify.
Do this insteadUse a state with a clear expected meaning, or combine bisection with tracing, a debugger, or additional checkpoints.
Common mistake Stopping after locating a broad region
What it looks likeConcluding that the bug is somewhere in the second half after one check.
Why it failsThe goal is to isolate the boundary between the last correct value and the first incorrect value.
Do this insteadRepeat bisection inside the remaining region until only a few lines separate the two checkpoints.
When Bisection Needs Support
Bisection is most straightforward when intermediate values clearly show whether execution is still correct. It becomes harder when a loop changes a data structure in complex ways, when no single checkpoint gives an interpretable state, or when the error depends on the order of operations or the interaction between multiple variables. In these cases, bisection still encourages useful partitioning of the problem, but it may not identify the full cause by itself.
Use bisection to reduce the region first, then add the technique that makes the remaining behavior visible. Step-by-step execution tracing, a debugger, or multiple checkpoints can help when one intermediate value is insufficient.
Key Takeaways
- 1Checking every line is a linear strategy and can require one check for each possible line.
- 2Bisection uses an intermediate checkpoint to eliminate about half of the remaining search space.
- 3The practical checkpoint should follow logical code structure and produce a state that is easy to verify.
- 4The debugging target is the boundary between the last correct intermediate value and the first incorrect one.
- 5Bisection is powerful but may need tracing, a debugger, or additional checkpoints for complex state and multi-variable interactions.
At a glance
- Linear debugging checks possible fault locations one by one, while bisection repeatedly halves the search space.
- A 100-line program may take up to 100 linear checks but about 7 bisection checks.
- In loops, place checkpoints at meaningful and verifiable states rather than insisting on exact line-number midpoints.
- Continue narrowing until the boundary between the last correct and first incorrect intermediate values is isolated.
- Use supporting debugging techniques when complex state or interactions make a single checkpoint difficult to interpret.