The shape of the lesson
By the end of the lesson, learners can
- Throw away half: In the lab, search for a value and step through.
- Write it in pseudocode: Exam questions ask you to write a binary search as a function that returns the index of the item, or −1 if it is not there.
- How fast is fast?: The syllabus asks how the performance of a binary search varies with the number of items.
- Conditions: sorted data in a structure with direct access by index.
- Mid:
(Low + High) DIV 2; compare List[Mid] with the search item. - Move: item larger means
Low ← Mid + 1; smaller meansHigh ← Mid - 1. - Stop: found, or Low > High. Worst case
INT(log2 n) + 1comparisons.
One picture every idea returns to
A binary search only works on data that is sorted and held in a structure with direct access by index, such as an array. It compares the search item with the middle element, Mid ← (Low + High) DIV 2. If they match, the item is found; if the middle item is smaller, the search continues in the upper half (Low ← Mid + 1); otherwise in the lower half (High ← Mid - 1). It stops when the item is found or Low > High. Each comparison halves the items left, so the worst case for n items is about log2 n comparisons: 1000 items need at most 10.
Forty-five minutes, phase by phase
| Time | Phase | What happens in the room | Grouping |
|---|---|---|---|
| 0 to 5 min | Hook: predict | Open with the question in the title, Halve it, again.. A binary search finds an item in a sorted list by checking the middle item and throwing away the half that cannot hold it. Put the figure on the board: it is the one picture every idea in the lesson returns to. | Whole class, then pairs |
| 5 to 13 min | Teach and check: Throw away half | In the lab, search for a value and step through. Project tab 3 of the lab (Binary search) and let a student drive it while the class predicts. Model the worked example Trace a search that fails on the board, one line at a time. Your turn: Using the same array, which elements are compared, in order, when searching for 70? | Whole class, then pairs |
| 13 to 21 min | Teach and check: Write it in pseudocode | Exam questions ask you to write a binary search as a function that returns the index of the item, or −1 if it is not there. Model the worked example Even-length list on the board, one line at a time. Your turn: For the same array, what is returned when SearchItem = 6, and what are Low and High when the loop ends? | Pairs |
| 21 to 30 min | Teach and check: How fast is fast? | The syllabus asks how the performance of a binary search varies with the number of items. Model the worked example Doubling the data on the board, one line at a time. Your turn: What is the largest number of items a binary search can always handle in at most 6 comparisons? | Round Table |
| 30 to 36 min | Check | The four Stage 1 questions from the student lesson, answered on mini whiteboards or by show of fingers. Re-teach the one most get wrong. | Individual, then whole class |
| 36 to 43 min | Plenary | The exam-style questions from Stage 2, one at a time: thirty seconds alone, then a random call. The feedback lines in the key give the examiner's wording. | Individual, random call |
| 43 to 45 min | Exit and homework | Set the worksheet below (6 questions, 23 marks). Learners self-assess against the objectives before they leave. | Individual |
Protect the parts that carry the learning
The sequence carries about fifty minutes of material, so the lab is driven by one student while the class predicts rather than explored freely. Times are a guide.
Protected: the check at 30 minutes. It is the only individual read on whether the key idea landed, and it is not cut.
Cut first if the build overruns: the last check in How fast is fast?, never the check or the plenary.
In a 60 minute block: run worksheet questions 1 to 3 in class as a Rally Coach set and model both the hardest worked example and its check live.
Round Table
One sheet travels round the team. Each student adds one line of working or one idea and passes it on, so the solution is built four hands at a time and every contribution is visible.
The full structure, with its variations and the other twelve, is on the cooperative-learning page.
What to head off, and how
| Trap learners fall into | Teaching move that pre-empts it |
|---|---|
| "A binary search splits the list in half" is not enough for the marks. | Say what is compared (the middle item with the search item) and what is discarded (the half that cannot contain it, because the data is sorted). |
| Do not use the loop condition Low < High. | When the item is in the last element left (Low = High) the loop would stop without checking it. |
| Do not say a binary search is "always faster". | It needs sorted data, and on a tiny list, or when the item is the first element, a linear search can need fewer comparisons. |
Binary search: worksheet
6 questions, 23 marks. Written in the style of the papers; no past paper question is reproduced.
Describe how a binary search finds an item in a 1D array, and state one condition that must be met before it can be used.
Names : ARRAY[1:9] holds Ade, Bo, Cy, Dev, Eva, Fin, Gus, Hal, Ivy. Complete a trace table (Low, High, Mid, Names[Mid]) for a binary search for Gus and state the index returned.
Using the same array, trace a binary search for Ali. State the final values of Low and High and the value returned.
Codes : ARRAY[0:99] OF STRING is a global array sorted into ascending order. Write pseudocode for a function FindCode(Target : STRING) RETURNS INTEGER that uses a binary search and returns the index of Target, or −1 if it is not present.
A sorted file of 6000 records is loaded into an array. Calculate the maximum number of comparisons needed by (a) a linear search (b) a binary search. Show your working for (b).
A list of 12 product codes is unsorted and is searched once a day. A student suggests sorting it so that a binary search can be used. Evaluate this suggestion.
Answer key and marking notes
- Find the middle element (Mid = (Low + High) DIV 2) and compare it with the search item.
- If equal, the item is found and its index is returned.
- If the middle item is less than the search item, discard the lower half (Low = Mid + 1), otherwise discard the upper half (High = Mid − 1); repeat with the remaining half.
- Stop when found or when Low > High (not found). Condition: the array must be sorted (in the order used for the comparison).
- Low 1, High 9, Mid 5, Eva (Eva < Gus, Low ← 6).
- Low 6, High 9, Mid 7, Gus.
- Gus = Gus, so Found is TRUE and the loop stops.
- Index 7 is returned after 2 comparisons.
- Mid 5 (Eva > Ali, High ← 4); Mid 2 (Bo > Ali, High ← 1); Mid 1 (Ade < Ali, Low ← 2).
- Final Low = 2, High = 1, so Low > High and the loop ends.
- −1 is returned (not found) after 3 comparisons.
- Function header with parameter and
RETURNS INTEGER, matchingENDFUNCTION. - Initialise Low ← 0 and High ← 99 (and a Found flag if used).
- Loop
WHILE Low <= High(and not found). Mid ← (Low + High) DIV 2inside the loop.- Compare Codes[Mid] with Target: equal means found / return Mid; less than means
Low ← Mid + 1; greater meansHigh ← Mid - 1. - Return −1 after the loop if not found.
- (a) 6000.
- (b) 212 = 4096 ≤ 6000 < 8192 = 213, so INT(log2 6000) = 12.
- Worst case 12 + 1 = 13 comparisons.
- A binary search needs sorted data, so the list would first have to be sorted, which takes far more operations than one search.
- With only 12 items, a linear search needs at most 12 comparisons against 4 for a binary search: a tiny saving.
- Conclusion: not worthwhile; a linear search is simpler and adequate (sorting pays off only for large data searched many times).
6 multiple-choice questions on this lesson
From the topic question bank. Assign them in the app for a marked score in your gradebook, or run the topic as a class game.
During a binary search Low = 7 and High = 20. The middle is found with Mid ← (Low + High) DIV 2. What is Mid?
- A13
- B13.5
- C14
- D27
Values : ARRAY[1:12] OF INTEGER holds 4, 9, 15, 22, 28, 31, 37, 44, 50, 56, 63, 71 in that order. A binary search (Low ← 1, High ← 12, Mid ← (Low + High) DIV 2) looks for 56. Which values are compared with 56, in order?
- A31, 50, 63, 56
- B6, 9, 11, 10
- C37, 56
- D31, 63, 56
To which of these can a binary search be applied directly?
- AA 1D array of names held in alphabetical order
- BA linked list of names held in alphabetical order
- CA 1D array of names in the order they were entered
- DA serial file of names held in alphabetical order
What is the maximum number of comparisons a binary search makes on a sorted array of 300 items?
- A9
- B8
- C150
- D300
Values : ARRAY[1:12] holds 4, 9, 15, 22, 28, 31, 37, 44, 50, 56, 63, 71. A programmer writes the loop as WHILE Low < High AND Found = FALSE instead of Low <= High; the rest of the binary search is correct. Searching for which value wrongly returns −1?
- A56
- B31
- C50
- D15
Values : ARRAY[1:12] holds 4, 9, 15, 22, 28, 31, 37, 44, 50, 56, 63, 71. The correct binary search (loop while Low <= High AND Found = FALSE) looks for 40. How many comparisons are made, and what are Low and High when the loop ends?
- A4 comparisons; Low = 8, High = 7
- B3 comparisons; Low = 8, High = 8
- C4 comparisons; Low = 7, High = 7
- D12 comparisons; Low = 13, High = 12
Quiz key
7 + 20 = 27 and 27 DIV 2 = 13, because DIV discards the remainder. 13.5 is ordinary division, 14 rounds up instead of discarding the fraction, and 27 forgets to divide by 2.
Mid = 13 DIV 2 = 6 (31 < 56, Low ← 7); Mid = 19 DIV 2 = 9 (50 < 56, Low ← 10); Mid = 22 DIV 2 = 11 (63 > 56, High ← 10); Mid = 10 (56, found). 6, 9, 11, 10 are the indices Mid takes, not the values compared. 37, 56 rounds 6.5 up to 7 instead of using DIV. 31, 63, 56 skips the comparison with element 9.
An array gives direct access to element Mid, and alphabetical order means half the names can be discarded after each comparison. A linked list and a serial file are sorted but must be followed from the start to reach the middle, and an array in entry order is not sorted, so discarding half would be wrong.
28 = 256 ≤ 300 < 512, so INT(log2 300) = 8 and the worst case is 8 + 1 = 9. 8 forgets the last comparison when one item is left, 150 assumes a single halving, and 300 is the worst case of a linear search.
For 56, Low reaches 10 and High 10 after comparing 31, 50 and 63; the loop then stops because 10 < 10 is FALSE, so element 10 (which holds 56) is never checked and −1 is returned. 31 is the first Mid, 50 is found when Low = 7 and High = 12, and 15 is found when Low = 1 and High = 5, so each is found before Low and High meet.
Mid 6 (31 < 40, Low ← 7), Mid 9 (50 > 40, High ← 8), Mid 7 (37 < 40, Low ← 8), Mid 8 (44 > 40, High ← 7). Now Low = 8 > High = 7, so the loop ends after 4 comparisons. Stopping at 3 leaves element 8 unchecked, Low = 7 and High = 7 would still allow another pass, and 12 comparisons is a linear search.
What to project
The student lesson embeds these tabs. Open them full screen on the projector; every slider has a drag handle on the stage.
Slides for this lesson
A projectable deck for every pack is on the way. Until then, present the student lesson full screen: its sections, figure and lab tabs follow the same order as the plan above.