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.
First check: Check an intermediate result that divides the program into two broad regions. The remaining search is about 50 lines.
Second check: Check the middle of that remaining region. The search is reduced to about 25 lines.
Third check: Another division leaves about 12 or 13 lines.
Fourth check: The suspect region is reduced to about 6 or 7 lines.
Fifth check: The remaining region is about 3 or 4 lines.
Sixth 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.
Check an early stage: If the intermediate result is correct, the problem is probably in a later region of the processing flow.
Check a later stage: If the later intermediate result is incorrect, the bug lies between the last correct checkpoint and this first incorrect checkpoint.
Repeat 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
Checking every line automatically
A 100-line program can require up to 100 checks with this approach.
Fix:
Begin with a checkpoint that divides the likely search region, then continue inside the region shown to contain the problem.Treating the exact middle line as mandatory
The exact midpoint may be unclear or impossible to verify.
Fix:
Choose a location based on logical code structure and ease of verification.Printing values that cannot be judged
The output does not help decide which half of the search region contains the bug.
Fix:
Inspect an intermediate value with a clear expected meaning.Assuming every bug is one incorrect value
Some bugs are about order or interactions rather than a single incorrect value.
Fix:
Use 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
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
- Identify an intermediate value or result that can be checked.
- Place a checkpoint that divides the likely bug region into two meaningful parts.
- Decide whether the checkpoint is correct or incorrect.
- Discard the region that cannot contain the bug.
- Repeat until the boundary between the last correct checkpoint and the first incorrect checkpoint is isolated.
- If 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.