Using Print Statements for Debugging
Debugging by bisection cuts debugging time from linear to logarithmic by eliminating half the search space with each checkpoint check.
The Cost of Checking Every Line
When a program produces a wrong result, a natural response is to inspect each line in order until something looks wrong. This is a linear search through the program: the search may move from the first line to the second, then the third, and so on. In a 100-line program, this approach can require up to 100 checks in the worst case.
Halving the Search Space
Bisection debugging divides the remaining suspect code into two regions. You check an intermediate value, then decide which region contains the problem. If the intermediate value is correct, the bug must be later. If it is incorrect, the bug must be earlier. You then repeat the same process inside the remaining region.
Reducing a 100-line search
A 100-line program produces an incorrect result. Compare the remaining search area after successive bisection checks.
- 1First check
Check an intermediate result that divides the program into two broad regions. The remaining search is about 50 lines.
- 2Second check
Check the middle of that remaining region. The search is reduced to about 25 lines.
- 3Third check
Another division leaves about 12 or 13 lines.
- 4Fourth check
The suspect region is reduced to about 6 or 7 lines.
- 5Fifth check
The remaining region is about 3 or 4 lines.
- 6Sixth check
Only one or two lines remain as the likely location.
A 100-line program can be narrowed to one or two likely lines in about six checks, or about seven checks when accounting for the final isolation.
Finding the Correctness Boundary
The most useful question is not simply “Which line is wrong?” It is “Where does the program change from producing correct intermediate values to producing incorrect ones?” Bisection searches for this boundary. The last correct checkpoint tells you that the earlier region has produced an acceptable result. The first incorrect checkpoint tells you that the transition happened before or at that point.
A boundary in a data-processing loop
A loop processes data and eventually produces a wrong result. You can inspect the result after selected stages of the loop.
- 1Check an early stage
If the intermediate result is correct, the problem is probably in a later region of the processing flow.
- 2Check a later stage
If the later intermediate result is incorrect, the bug lies between the last correct checkpoint and this first incorrect checkpoint.
- 3Repeat inside the region
Add or move a checkpoint within that suspect region and continue narrowing it.
The bug is isolated to the small region between the last correct intermediate value and the first incorrect one.
Checkpoints Inside Loops
An exact midpoint is often impractical. A loop may not have a convenient place to inspect a value at the exact middle line of a program. Instead, place checkpoints according to the loop's logical flow. Useful locations can include after the loop completes, at the end of an iteration, or after a key calculation. The objective is to divide the likely bug region into two reasonably balanced parts based on how the program works, not merely on line counts.
For a loop that processes data and produces a result, first consider checkpoints after a meaningful processing stage. If that does not distinguish the correct and incorrect regions, inspect the end of an iteration or the result immediately after a key calculation. Select the location that makes the intermediate value easiest to verify.
Estimating the Number of Checks
To estimate the checks needed, imagine repeatedly cutting the remaining search region in half until only one or two possible lines remain. For 100 lines, the sequence is approximately 100, 50, 25, 12 or 13, 6 or 7, 3 or 4, and finally 1 or 2. This gives about 7 checks. For 1000 lines, linear search may require up to 1000 checks, while bisection requires about 10 checks.
| 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 examples show how repeated halving reduces the number of checks as program size grows.
Common Mistakes
Common mistake Checking every line automatically
What it looks likeStarting at the first line and inspecting each line in sequence without using intermediate checkpoints.
Why it failsA 100-line program can require up to 100 checks with this approach.
Do this insteadBegin with a checkpoint that divides the likely search region, then continue inside the region shown to contain the problem.
Common mistake Treating the exact middle line as mandatory
What it looks likeTrying to place a checkpoint at an exact line midpoint even though a loop has no meaningful value to inspect there.
Why it failsThe exact midpoint may be unclear or impossible to verify.
Do this insteadChoose a location based on logical code structure and ease of verification.
Common mistake Printing values that cannot be judged
What it looks likeAdding a checkpoint without knowing what the intermediate value should mean or whether it is correct.
Why it failsThe output does not help decide which half of the search region contains the bug.
Do this insteadInspect an intermediate value with a clear expected meaning.
Common mistake Assuming every bug is one incorrect value
What it looks likeUsing only one value check when the problem may involve operation order or interactions between multiple variables.
Why it failsSome bugs are about order or interactions rather than a single incorrect value.
Do this insteadUse bisection as a narrowing strategy and combine it with step-by-step tracing, a debugger, or multiple checkpoints when necessary.
When Bisection Needs Help
Bisection is not always easy to apply. A complex data structure may be difficult to verify at one intermediate point. Some bugs depend on the order of operations or on interactions between several variables rather than on one incorrect value. In such cases, bisection still provides a useful way to partition the problem, but it may need to be combined with step-by-step execution tracing, a debugger, or multiple checkpoints.
Practice the Search
A program has 1000 lines and produces an incorrect final result. Describe how you would use checkpoint checks to narrow the search. Then explain why choosing a meaningful checkpoint in a loop may be better than choosing the exact middle line by number.
Hints
- Compare the worst-case number of checks for line-by-line search with bisection.
- Imagine reducing the remaining region from 1000 to about 500, then about 250, and so on.
- For a loop, consider the end of an iteration, after a key calculation, or after the loop completes.
What do you think happens?
A 100-line program is debugged by checking an intermediate result, then repeatedly checking the middle of the remaining suspect region. Which approach is expected to require fewer checks in the worst case?
Reveal answer
Repeatedly halving the suspect region
The source example gives up to 100 checks for linear search and about 7 checks for bisection.
A Systematic Debugging Habit
- 1Identify an intermediate value or result that can be checked.
- 2Place a checkpoint that divides the likely bug region into two meaningful parts.
- 3Decide whether the checkpoint is correct or incorrect.
- 4Discard the region that cannot contain the bug.
- 5Repeat until the boundary between the last correct checkpoint and the first incorrect checkpoint is isolated.
- 6If the values are difficult to verify or the bug involves interactions or operation order, add tracing, a debugger, or multiple checkpoints.
Key Takeaways
- Checking every line in order is a linear search and can require up to 100 checks for a 100-line program.
- Bisection reduces the search region by about half after each useful checkpoint.
- A 100-line program can be narrowed to about one or two lines in roughly six checks, or about seven checks overall.
- Checkpoint locations should follow logical code structure and ease of verification, especially inside loops.
- The target is the boundary between the last correct intermediate value and the first incorrect one.