← WA Computer Science ATAR Unit 1

Tracing a binary search

Each row of a binary search trace table updates low, high and mid. The range halves each step until the target is found or low becomes greater than high.

Part of: WA Computer Science ATAR Year 11 — Standard Algorithms — Module 24

Understanding Tracing a binary search in WA Computer Science ATAR Unit 1

What it does: The middle value is too small, so every item at or below mid is ruled out. Low moves to mid + 1, which gives a new row in the trace table. 8 DIV 2 = 4, so the first row of the trace table has mid = 4 and list[4] = 15. 21 is greater than 15, so the target must be in the upper half. Low moves up to mid + 1 = 5 and the range shrinks. 12 DIV 2 = 6. list[6] = 27, which is greater than 21, so high becomes 5 on the next row.

Common mistakes: Pseudocode lists start at index 1, so the first row of the trace table must have low ← 1. Starting at 0 gives the wrong first mid (4 instead of 5). The middle index is found by adding low and high, then using DIV 2. Subtracting gives a negative number, not the middle. It should be mid ← (low + high) DIV 2.

Class: _____________________  ·  Name: _____________________  ·  Date: _________

Free printable worksheet with full answer key — or add this module to a class and your students practise it interactively.

🖨 Print worksheet + answer key Add Tracing a binary search to a class →

This module's key terms are also in a printable crossword (Modules 100–314) and word search (Modules 100–470).

Take this worksheet further — free with Cloodit

Each concept is reinforced from every angle — learned, then applied, then tested.

Learning
Duo
List: [3, 8, 12, 15, 21, 27, 34] (indexes 1 to 7). With low = 1 and high = 7, what is the first mid?
mid = 4, because (1 + 7) DIV 2 = 4mid = 3, because (1 + 7) DIV 2 = 3
Matches
IF list[mid] < target THEN low ← mid
↓
Low should be set to mid + 1, not mid. Mid has already been checked, so the range may never shrink and the trace table repeats forever.
Applying
Meanings
Term
mid ← (low + high) DIV 2
Meaning
Each row of a binary search trace table updates low, high and mid. The range halves each step until the target is found or low becomes greater than high.
Practice
low ← 0
Testing
Gaps
mid ← (low + high) 2
Check Answer
Spots
1n ← 9
2low ← 0

Cloodit turns curriculum-aligned coding content into journeys students work through one biome at a time.

The 'Dumbo Octopus' badge — Module Maker, one of Cloodit's 106 collectible badges
Students earn collectable badges

Over 100 of them, across seven natural biomes.

Study Buddy
Students build a real study resource

Turns their work into revision material ready for Flash Cards and Exam study.

Diamond Dash — one of Cloodit's live, competitive Sprint games
Students lock in with Sprints

Live, competitive practice for the start of the lesson or a teacher-led lesson finisher.

A Cloodit certificate of achievement, ready to personalise and print
Custom printable certificates

Honour your top performers, or encourage a student who's trying hard — ready to print in seconds.

Add to class →

Quick Questions

1. List: [3, 8, 12, 15, 21, 27, 34] (indexes 1 to 7). With low = 1 and high = 7, what is the first mid?
A. mid = 3, because (1 + 7) DIV 2 = 3
B. mid = 4, because (1 + 7) DIV 2 = 4 ✓
8 DIV 2 = 4, so the first row of the trace table has mid = 4 and list[4] = 15.
2. Searching for 21 in the same list: mid = 4 and list[4] = 15. What does the next row of the trace table show?
A. high becomes 3, because 21 is greater than 15
B. low becomes 5, because 21 is greater than 15 ✓
21 is greater than 15, so the target must be in the upper half. Low moves up to mid + 1 = 5 and the range shrinks.
3. Searching for 21: low = 5 and high = 7. What is mid for this row?
A. mid = 6, because (5 + 7) DIV 2 = 6 ✓
B. mid = 5, because (5 + 7) DIV 2 = 5
12 DIV 2 = 6. list[6] = 27, which is greater than 21, so high becomes 5 on the next row.
4. The range is low = 1 and high = 6. What is mid?
A. mid = 3, because 7 DIV 2 drops the .5 ✓
B. mid = 4, because 7 DIV 2 rounds up
DIV is whole-number division and it drops the remainder, so 7 DIV 2 = 3.
5. Searching for 10 in [3, 8, 12, 15, 21, 27, 34]: mid = 2 and list[2] = 8. What happens to low and high?
A. low ← mid + 1, so low = 3 ✓
B. high ← mid - 1, so high = 1
10 is greater than 8, so the search moves to the upper half. Low becomes 3 and high stays the same.

Match the Pairs

mid ← (low + high) DIV 2 → Finds the middle index of the current search range, rounding down to a whole number
low > high → The range is empty, so the target is not in the list and the search stops
The target is greater than the middle item, so the search moves to the upper half of the range → IF list[mid] < target THEN low ← mid + 1
The target is smaller than the middle item, so the search moves to the lower half of the range → IF list[mid] > target THEN high ← mid - 1
IF list[mid] < target THEN low ← mid → Low should be set to mid + 1, not mid. Mid has already been checked, so the range may never shrink and the trace table repeats forever.
Start: low ← 1, high ← 8, mid ← 4. Trace stops when low = high → The search should stop when low is greater than high, not when they are equal. When low equals high there is still one item left to check.

Key Term

mid ← (low + high) DIV 2
Each row of a binary search trace table updates low, high and mid. The range halves each step until the target is found or low becomes greater than high.

Fill in the Blanks

1. mid ← (low + high) DIV 2
Hint: Type the operator that gives whole-number division, so mid is always an integer index.
2. WHILE low ≤ high mid ← (low + high) DIV 2
Hint: Type the comparison operator that keeps the loop running while the search range still has items.
3. IF list[mid] < target THEN low ← mid + 1
Hint: Type the expression that moves low to just above mid, discarding the lower half.
4. ELSE IF list[mid] > target THEN high ← mid - 1
Hint: Type the variable that moves down when the middle value is too big, discarding the upper half.
5. IF low > high THEN OUTPUT "Not found"
Hint: Type the comparison operator showing the range has run out, meaning the target is not in the list.

Spot the Error

Question 1
A n ← 9
B low ← 0
C high ← n
D mid ← (low + high) DIV 2
Line B — Pseudocode lists start at index 1, so the first row of the trace table must have low ← 1. Starting at 0 gives the wrong first mid (4 instead of 5).
Question 2
A low ← 1
B high ← 9
C mid ← (low - high) DIV 2
D OUTPUT mid
Line C — The middle index is found by adding low and high, then using DIV 2. Subtracting gives a negative number, not the middle. It should be mid ← (low + high) DIV 2.
Question 3
A WHILE low ≤ high
B mid ← (low + high) DIV 2
C IF mid = target THEN
D found ← TRUE
Line C — mid is an index, not a value in the list. The algorithm must compare the item list[mid] with the target, so the line should be IF list[mid] = target THEN.
Question 4
A WHILE low > high
B mid ← (low + high) DIV 2
C OUTPUT low, mid, high
D ENDWHILE
Line A — The loop keeps going while the range is valid, which means low ≤ high. With low > high the loop would never start, so no trace rows would be produced.
Question 5
A IF list[mid] > target THEN
B high ← mid + 1
C ELSE
D low ← mid + 1
Line B — If list[mid] is bigger than the target, the target is in the lower half. mid has been checked, so the new high must be mid - 1, not mid + 1.

Student with a class code? Join your class →