Study Guide Instructor view
Binary Search
Teaching notes for Lesson 5.17, with controls for presenting it.
Keep this page on your own screen. Share only the lesson window. The lesson window holds no teaching notes, so sharing it cannot show them.
Presenting
- Open the lesson in its own window and share that window, not this one.
- Use Next and Previous here, or the lesson’s own, to move through the lesson. Next reveals one thing at a time: the next idea, or the answer to the question on screen, then the next step. Previous takes the last reveal back. The line below says what is on screen and what Next will show.
- Reveal hints and answers when the class is ready, and reset a demonstration before using it again.
The controls need JavaScript and a browser that supports BroadcastChannel. Without them, open the lesson in presentation mode and use its own controls.
The two windows talk to each other only inside this browser, on this device. Nothing is sent to a server, and no account is needed. A second device (a phone or another tablet) cannot follow the lesson window yet.
Now on the lesson window
- On screen
- Next teaching point
Guidance for this point
Lesson plan
- Level
- Intermediate
- Time
- About 75 minutes; the steps below add up to 95
Learners rediscover halving through a guessing game, apply it to a sorted locker list, trace it with Low, High and Mid (including a target that is missing), and compare it with a linear search by counting checks. The questions diagnose the usual faults: Low set to Mid instead of Mid + 1, the middle taken by value, and a search run on an unsorted list.
Objectives
- Explain why a binary search needs a sorted list and what it throws away at each check
- Work out the middle item with DIV(Low + High, 2) and update Low or High correctly
- Trace a binary search, including a target that is not in the list, with a trace table
- Compare a binary search with a linear search by counting the checks each needs
- Spot and correct a faulty binary search
- Write the pseudocode to count how many items a binary search looks at
Before the lesson
- A sorted list of 15 numbers on the board or on paper, and a counter or coin to mark Low, High and Mid.
- Mini whiteboards for trace-table answers.
- Optional: a deck of cards, sorted, to play the guessing game physically.
Steps
Introduction Opening
On the lesson window now
On screen: the lesson’s title, module and number; Next adds its objectives and key terms, as the lesson page lists them; Next again begins the first step.
Objectives on screen
- Explain why a binary search needs a sorted list and what it throws away at each check
- Work out the middle item with DIV(Low + High, 2) and update Low or High correctly
- Trace a binary search, including a target that is not in the list, with a trace table
- Compare a binary search with a linear search by counting the checks each needs
- Spot and correct a faulty binary search
- Write the pseudocode to count how many items a binary search looks at
Purpose: Learners rediscover halving through a guessing game, apply it to a sorted locker list, trace it with Low, High and Mid (including a target that is missing), and compare it with a linear search by counting checks. The questions diagnose the usual faults: Low set to Mid instead of Mid + 1, the middle taken by value, and a search run on an unsorted list.
1. Guess the number Think 6 min
On the lesson window now
Purpose: Learners meet the idea of ruling out half of the possibilities with each question before any algorithm is named.
Ask
- What is your first guess, and why?
- Why is 1 a poor first guess?
Responses to expect
- 50
- It rules out the most numbers whatever the answer is
Misconceptions to challenge
- A learner may believe: “Guessing 1 first is safest because it is the smallest.” Respond: Play it: if the answer is 73, guessing 1 only rules out one number. A guess in the middle rules out half whichever way the answer goes.
On the board or with the pen
- Write the range 1 to 100 and cross out half after each guess.
Checking understanding: Pairs play three rounds with a limit of seven guesses; ask who stayed within it, and how.
Depending on the answers
- If nearly every pupil guesses 50: move straight on and ask how many guesses are enough, then return to the answer after the counting step
- If pupils guess in steps of 10 or from 1 upwards: run the game once with the middle strategy and count the guesses against theirs
In the lesson window
- Think it through: What number would you guess first, and why? Roughly how many guesses do you think you would need, at most, to be sure of getting the answer?
2. Throwing away half the list Discover 8 min
On the lesson window now
Purpose: Transfer halving to a sorted list and name the middle-item idea as a binary search.
Ask
- Which position would you look at first, and what does 35 tell you about 47?
- Which items can you now ignore?
Responses to expect
- Position 8, because it has about the same number of items either side
- Everything at or before 35
Misconceptions to challenge
- A learner may believe: “The middle item is the one with the middle value.” Respond: It is the middle position. Ask which position has seven items before and seven after.
- A learner may believe: “After finding 35 you can ignore only 35.” Respond: Use the list order: everything before 35 is no bigger than 35, so none of it can be 47.
What learners should notice
- The list shrinks from 15 items to 7 after one check.
Checking understanding: The which-half question: the option that ignores only 35 shows who has not used the order.
Depending on the answers
- If several pupils choose the option that ignores the later lockers: point to the table and ask which side of 35 holds numbers bigger than 35
English as an additional language
- Practise the words smaller, bigger, before and after with the locker table.
In the lesson window
- Think it through: Using what you noticed in the guessing game, which position would you look at first to find 47 in this list? What would the number there tell you about where 47 could be?
- Check your understanding: The search for locker 47 checks the middle item, 35, in the sorted list above. What can the search now ignore?
3. Why the list must be in order Predict 6 min
On the lesson window now
Purpose: Pupils see for themselves that the comparison is only useful when the list is in order.
Ask
- Does knowing the middle item is 35 tell you anything when the list is unsorted?
- Why does sorted order make halving safe?
Responses to expect
- No, 47 could be anywhere
- Everything on one side is smaller and everything on the other bigger
Misconceptions to challenge
- A learner may believe: “A sorted list is needed because it uses less memory.” Respond: Sorting only changes the order. Ask what one comparison can tell you in each case.
- A learner may believe: “The computer cannot find the middle of an unsorted list.” Respond: The middle position comes from the positions, not the values. Ask what the value stored there tells you.
Checking understanding: Ask pupils to show a thumb up or down for “can I rule anything out?” on an unsorted list.
In the lesson window
- Think it through: Does knowing that the middle item is 35, which is smaller than 47, tell you anything about where 47 might be? Explain.
- Check your understanding: Why can a binary search only be used on a sorted list?
4. Keeping track: Low, High and Mid Explain 8 min
On the lesson window now
Purpose: Introduce Low, High and Mid and the reasoning for Mid + 1 and Mid - 1, as a worked example before the learner traces.
Ask
- Why does Low become Mid + 1 and not Mid?
- What does DIV do when the total is odd?
Responses to expect
- Because position 8 has been checked and cannot be the answer
- It drops the remainder
Misconceptions to challenge
- A learner may believe: “Mid should be 4.5 when Low is 1 and High is 8.” Respond: There is no position 4.5. DIV keeps the whole-number part.
- A learner may believe: “Low should become Mid so that no item is missed.” Respond: Mid has been checked. Keeping it in play can make the search repeat for ever.
On the board or with the pen
- Draw a number line of positions 1 to 15 and mark Low, High and Mid with arrows, moving Low across as the example is read.
Checking understanding: The mid-position check: DIV(9, 2) tests understanding of DIV in this context.
Depending on the answers
- If pupils choose 5 or 4.5: recall DIV from Lesson 9 with DIV(7, 2) and DIV(9, 2) on the board, then retry
- If pupils are comfortable: ask them to predict the next Mid before the trace appears
In the lesson window
- Check your understanding: In another search, Low is 1 and High is 8. What is Mid, using DIV(Low + High, 2)?
5. The whole algorithm Explain 8 min
On the lesson window now
Purpose: Show the whole algorithm in pseudocode and a trace, one pass at a time.
Ask
- Why does the loop condition have two parts?
- Where is the answer when the target is found?
Responses to expect
- Found = FALSE and Low <= High: stop when found or when nothing is left
- In Mid, because the loop stops without changing it
Misconceptions to challenge
- A learner may believe: “Mid is wrong after the loop because it was changed.” Respond: The loop stops straight after Found becomes TRUE, so Mid still holds the position.
On the board or with the pen
- Underline Found = FALSE in one colour and Low <= High in another.
Support
- Give pupils a printed trace table to fill alongside the StepThrough.
Stretch
- What would happen if the condition were only Found = FALSE and the target were missing?
In the lesson window
- Check your understanding: In pass 2 of the search for 47, Lockers[12] is 58. Why does High become 11, and not stay at 15 or become 12?
6. Trace it yourself Experiment 14 min
On the lesson window now
Purpose: Supported then independent tracing, including a target that is missing.
Ask
- What are Low, High and Mid on pass 2?
- Why does the search for 50 stop?
Responses to expect
- 9, 15 and 12
- Low (11) has become bigger than High (10), so no position is left
Misconceptions to challenge
- A learner may believe: “The search for 50 should stop when it reaches the middle of the list.” Respond: Nothing in the loop checks that. Ask what Low and High say about the positions left.
- A learner may believe: “Both Low and High should change on every pass.” Respond: Only one of them changes: Low when the middle was too small, High when it was too big.
Checking understanding: Pupils write the row for pass 3 of the second table on a mini whiteboard before the class reveals it; compare Mid and the comparison separately.
Depending on the answers
- If a pupil gets Mid wrong in pass 2: ask them to say Low + High, then halve with DIV; do it aloud
- If a pupil updates the wrong end: ask: is the middle item smaller or bigger than the target, so which half can go?
- If most trace correctly: ask them to explain what Low > High means before the check question
Support
- Offer the first two columns pre-filled for pupils who need the shorter task.
English as an additional language
- Use a gesture: hand for Low and High moving inwards.
In the lesson window
- Check your understanding: In the search for 50, why does the loop end after pass 4 when no item equalled 50?
7. How many checks, at most? Discover 10 min
On the lesson window now
Purpose: Pupils discover the doubling pattern and use it to count the most checks needed.
Ask
- After one check of 15 items, at most how many remain?
- How many checks for 100 items, and why 7 and not 6?
Responses to expect
- 7, then 3, then 1
- 7 checks cover 127 items, but 6 cover only 63
Misconceptions to challenge
- A learner may believe: “A list ten times bigger needs ten times the checks.” Respond: Doubling the list adds only one check. Look at the doubling table.
- A learner may believe: “A binary search looks at half the items.” Respond: It halves what is left at every check, repeatedly. Ask how many times 1000 can be halved.
Checking understanding: The thousand-items check: choosing 500 or 100 shows who has not seen the doubling.
Depending on the answers
- If pupils cannot continue the table: ask them to double and add one on a mini whiteboard for 8, 9 and 10 checks
- If pupils continue easily: ask for the number of checks for a million items, then compare with 1 000 000 for a linear search
To go further
- Why is the most checks for 100 items the same as for 127?
In the lesson window
- Think it through: A sorted list has 15 items. After the first check of the middle item, at most how many items can still be the answer? After the second check? After the third? What does that tell you about the most checks needed for 15 items?
- Check your understanding: A sorted list has 1000 items. Using the pattern in the table (7 checks cover 127 items, and each check doubles and adds 1), what is the most checks a binary search needs?
8. Comparing two algorithms Explain 10 min
On the lesson window now
Purpose: Compare two algorithms for the same problem on the same measure, and meet the misconception about “middle” and “always quicker”.
Ask
- Does a binary search always beat a linear search?
- When would a linear search be quicker?
Responses to expect
- No: not when the target is first, or when the list is not sorted
- When the target is early in the list
Misconceptions to challenge
- A learner may believe: “A binary search is always quicker.” Respond: Ask about a target that is the first item, and about a list that is not sorted.
- A learner may believe: “The middle item is the one with the middle value.” Respond: In 1, 2, 3, 100, 200 the middle position holds 3.
On the board or with the pen
- Two columns, linear and binary, with the worst-case counts for 15, 100, 1000 and a million items.
Checking understanding: The 600 pupil numbers question: the two extreme options show who compares on the worst case only.
Depending on the answers
- If pupils choose the option that says always: ask for a target in position 1 of a sorted list and count checks for each search
In the lesson window
- Apply it: A fictional school office keeps its 600 pupil numbers sorted, and checks one number each morning. A technician says: “A binary search will always beat a linear search, because it looks at fewer items.” Which reply is most accurate?
9. Spot the mistake Apply 8 min
On the lesson window now
Purpose: Diagnose two faults: an update that does not move past the item just checked, and a search run on an unsorted list.
Ask
- What does Low ← Mid do on the two-item list?
- Where was 20 in Priya’s list, and which half did the search throw away?
Responses to expect
- Low stays 1, so Mid stays 1 and the loop never ends
- Position 4, in the half it had thrown away
Misconceptions to challenge
- A learner may believe: “Priya’s search should still find 20 because it is in the list.” Respond: The search only looks where the comparisons send it. Trace Mid 3, then Mid 1.
Checking understanding: Pupils trace Sam’s version for two passes to see Low stay at 1.
Depending on the answers
- If pupils cannot see the repeat: write Low, High and Mid for three passes and ask what is different on each
In the lesson window
- Apply it: A sorted list has two items, 10 and 20, in positions 1 and 2, and the target is 20. Low is 1, High is 2, Mid is DIV(3, 2) = 1, and Lockers[1] is 10. What happens with Sam’s update?
- Apply it: Low starts at 1 and High at 5. What does the program output, and what does this show?
10. Counting the checks in code Apply 10 min
On the lesson window now
Purpose: Writing: add a counter to the algorithm and predict its output for a found and a missing target.
Ask
- Which line looks at an item, and so where does the counter go?
- What is the output for 47 and for 50?
Responses to expect
- Straight after Mid is worked out
- 3 for 47 and 4 for 50
Misconceptions to challenge
- A learner may believe: “The counter should be set to 0 inside the loop.” Respond: It would reset every pass. Set it once, before the loop.
Checking understanding: Pupils swap pseudocode and check the counter is initialised before the loop and increased once per pass.
Support
- Provide the algorithm with a gap where the two Checked lines belong.
Stretch
- Write the algorithm for a list of 100 items, and say what changes.
In the lesson window
- Think it through: Change the pseudocode of the whole algorithm so that it also counts how many items the search looks at, and outputs that number at the end. Then say what it would output for the target 47 in the locker list, and for 50.
11. Show what you know Consolidate 7 min
On the lesson window now
Purpose: Explanation, choice of algorithm in a new context and an honest statement of what is still unclear.
Ask
- Explain a binary search to a friend using the guessing game.
- Which search should the shop use, and why?
Responses to expect
- Check the middle, throw away half, repeat; it needs sorted order
- A binary search, because the list is sorted and searched often
Misconceptions to challenge
- A learner may believe: “A linear search is the only one that works on numbers.” Respond: Both work on numbers. What is true about this list that a binary search can use?
Checking understanding: Collect the “least sure” questions: they decide how the next lesson starts.
Depending on the answers
- If several pupils are unsure about Mid - 1 and Mid + 1: trace the 50 search again on the board before the next lesson
In the lesson window
- Think it through: Explain to a friend how a binary search finds an item in a sorted list, and why it is so much quicker than a linear search on a long list. Use the guessing game or a list of your own.
- Apply it: A fictional shop keeps 10 000 product codes in order from smallest to largest, and its tills look up a code hundreds of times a day. The list changes once a week. Which search should the tills use, and why?
- Think it through: Which part of this lesson are you least sure about? Write one question you would ask your teacher.
Lesson recap Closing
On the lesson window now
On screen: the lesson’s objectives again; Next adds the closing question, which asks the class to explain each one in their own words without looking back. It says nothing about what anyone has learnt: use the answers to decide what to revisit.
Points to listen for
- A binary search needs a sorted list: it checks the middle item and throws away the half that cannot hold the target.
- Mid is DIV(Low + High, 2); Low becomes Mid + 1 or High becomes Mid - 1, and the loop ends when found or Low is bigger than High.
- Each doubling of the list adds one check: 100 items need at most 7, where a linear search might need 100.
- Compare algorithms on the same measure; the best algorithm depends on what is known about the data.
Consolidation
- A binary search needs a sorted list: it checks the middle item and throws away the half that cannot hold the target.
- Mid is DIV(Low + High, 2); Low becomes Mid + 1 or High becomes Mid - 1, and the loop ends when found or Low is bigger than High.
- Each doubling of the list adds one check: 100 items need at most 7, where a linear search might need 100.
- Compare algorithms on the same measure; the best algorithm depends on what is known about the data.