To trace an algorithm, you play the computer: write down every variable, update it line by line, and never skip a step. The three algorithms here give you three kinds of trace: a scan, a halving and a repeated swap.
This lesson follows working with arrays and structured data in advanced programming practice. For a general method, see tracing pseudocode step by step.
How does a linear search trace?
A linear search checks each element from the start until it finds the target or reaches the end. Search for 14 in the array [9, 14, 3, 14, 20].
| Step | i | data[i] | Equal to 14? |
|---|---|---|---|
| 1 | 0 | 9 | No |
| 2 | 1 | 14 | Yes, stop |
The search reports index 1 and never reaches the second 14 at index 3. If the target were 7, the trace would run through all five indexes and report not found.
How does a binary search trace?
A binary search keeps a low and high index, checks the middle and discards half. Search for 25 in the sorted array [3, 8, 12, 19, 25, 31, 40], indexes 0 to 6.
| Step | low | high | mid | data[mid] | Decision |
|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 19 | 19 < 25, so low = 4 |
| 2 | 4 | 6 | 5 | 31 | 31 > 25, so high = 4 |
| 3 | 4 | 4 | 4 | 25 | Found at index 4 |
The mid value uses whole-number division, so (0 + 6) ÷ 2 = 3 and (4 + 6) ÷ 2 = 5. Three comparisons find a value in seven elements, where a linear search could have needed five.
How does a bubble sort trace?
A bubble sort compares neighbours and swaps them if they are in the wrong order. Sort [5, 2, 4, 1] into ascending order.
| Pass | Comparisons and swaps | Array after the pass |
|---|---|---|
| 1 | 5,2 swap; 5,4 swap; 5,1 swap | 2, 4, 1, 5 |
| 2 | 2,4 no swap; 4,1 swap | 2, 1, 4, 5 |
| 3 | 2,1 swap | 1, 2, 4, 5 |
After each pass the largest unsorted value has reached its place, so each later pass needs one fewer comparison. Four values need three passes here.
The mistake that breaks binary search
A common slip is to use binary search on an array that is not sorted. Every step is carried out correctly, but the answer is wrong.
Search for 3 in the unsorted array [12, 3, 25, 8, 19].
| Step | low | high | mid | data[mid] | Decision |
|---|---|---|---|---|---|
| 1 | 0 | 4 | 2 | 25 | 25 > 3, so high = 1 |
| 2 | 0 | 1 | 0 | 12 | 12 > 3, so high = −1 |
| 3 | 0 | −1 | low > high, stop: not found |
The 3 sits at index 1, yet the search reports not found. Binary search assumes everything right of the middle is larger, and that is false here. Sort the array first, or use a linear search.
A routine for any trace
- Write the array with its indexes.
- Create a column for every variable that changes, plus the comparison.
- Update one row per step, copying the array when it changes.
- Stop only when the loop condition in the code says to stop, not when you think you have the answer.
Check yourself
Trace a binary search for 40 in the sorted array [4, 10, 17, 22, 35, 40, 51, 60], indexes 0 to 7. Give the mid index at each step.
Answer
Step 1: low = 0, high = 7, mid = (0 + 7) ÷ 2 = 3 using whole-number division. data[3] = 22, which is less than 40, so low = 4.
Step 2: low = 4, high = 7, mid = (4 + 7) ÷ 2 = 5. data[5] = 40, which equals the target.
The search stops at mid = 5 after 2 comparisons. Whole-number division rounds 3.5 down to 3 and 5.5 down to 5. If your language rounds differently, state the rule in your answer.
What to study next
A trace shows where a program goes wrong. The next skill is naming the kind of error: debugging syntax, logic and runtime errors. Keep practising with the restricted pseudocode trace trainer.
If you want a teacher to watch you trace a new algorithm, see online one-to-one Computer Science tuition.