Study Guide
Binary Search
How to find an item in a sorted list by checking the middle and throwing away half each time, traced step by step, written in pseudocode, and compared with a linear search by counting the checks each needs.
Lesson 5.17 Algorithms and Programming
For: Key Stage 3 learners (about ages 12 to 14) who have met loops, arrays and a linear search, and Cambridge IGCSE Computer Science learners wanting a second searching algorithm
Stage: Think
Guess the number
Two friends play a guessing game. One thinks of a whole number from 1 to 100. The other guesses, and after every guess the first friend says only “higher”, “lower” or “correct”. The game is fictional, but you may have played something like it.
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?
- Hint 1: Think about what a “higher” or “lower” tells you about all the numbers you have not guessed.
- Hint 2: Is there a first guess that rules out as many numbers as possible?
Show a model answer
A good first guess is 50. Whatever the answer, “higher” or “lower” rules out half of the numbers at once: after guessing 50, either 1 to 50 or 51 to 100 is gone. Guessing 1 first would only rule out one number if it were wrong. Repeating the idea, the numbers left go from 100 to about 50, 25, 12, 6, 3 and 1, so seven guesses are always enough. You will see why in this lesson.
Stage: Discover
Throwing away half the list
A fictional school has 15 lockers, and a sorted list records the locker numbers in use, from smallest to largest. The list is stored in an array called Lockers.
Positions 1 to 15 hold these numbers, in order: 3, 8, 12, 17, 21, 26, 30, 35, 41, 47, 52, 58, 63, 70, 77. So position 1 holds 3, position 8 holds 35, position 10 holds 47 and position 15 holds 77.
The caretaker wants to know whether locker number 47 is in use. A linear search would start at position 1 and read on.
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?
- Hint 1: Which position has about the same number of items on each side of it?
- Hint 2: If the number there is smaller than 47, which items can you ignore?
Show a model answer
Position 8, which holds 35, has seven items before it and seven after it. Since 35 is smaller than 47 and the list is sorted from smallest to largest, every item at positions 1 to 8 is 35 or smaller, so 47 cannot be there. Only positions 9 to 15 are still possible: one check has thrown away more than half the list.
Checking the middle item, and using the answer to throw away the half that cannot hold the target, then repeating on the half that is left, is a binary search. The “binary” refers to the two halves: at every check there are two ways to go, up or down. Each check leaves at most half of the items still in play, so the list shrinks very quickly.
Check your understanding
Show the answer
Answer: B. Locker 35 and every locker before it, because 47 is bigger than 35.
When the middle item is smaller than the target, the target can only be in the items after the middle one; when it is bigger, only in the items before it.
Stage: Predict
Why the list must be in order
Now imagine that the locker list was not in order, and the caretaker looked at the middle item and found 35 again. The list begins 52, 3, 70, 17, 35, …
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.
- Hint 1: Could 47 be before the 35, in a list that is in no order?
Show a model answer
No. With no order, 47 could be anywhere: before the 35 or after it. The middle item being smaller than 47 says nothing about the other items, so no part of the list can be thrown away. The “higher or lower” answer only helps when the list is in order.
Check your understanding
Show the answer
Answer: C. The “bigger” or “smaller” answer only shows which half to keep in a sorted list.
The sorted order is what makes “throw away half” safe. A binary search on a list that is not sorted can miss an item that is really there.
Stage: Explain
Keeping track: Low, High and Mid
A program cannot look at a list the way a person does. It needs to remember which part of the list is still possible. It does this with two position numbers, Low (the first position still possible) and High (the last position still possible), and finds the middle position, Mid, between them:
Mid ← DIV(Low + High, 2)
DIV gives the whole-number part of a division and drops the remainder (Lesson 9). The first time, Low is 1 and High is 15, so Mid is DIV(16, 2), which is 8.
The target is 47. Low is 1, High is 15, so Mid is 8, and Lockers[8] is 35.
- Compare the middle item with the target. 35 is smaller than 47.
- Decide which part can be thrown away. The target is bigger than the middle item, so it can only be after position 8. Positions 1 to 8 are no longer possible.
- Move Low just past the middle. Low becomes 9, which is
Mid + 1. WritingLow ← Midwould keep position 8 in play, even though it has been checked. - If the middle item were bigger than the target, the target could only be before it, and High would become
Mid - 1, for the same reason. - If the middle item equals the target, the search has found it and stops.
The next Mid is DIV(9 + 15, 2), which is 12.
Check your understanding
Show the answer
Answer: A. 4, because DIV(9, 2) gives the whole-number part of 4.5.
A search always has a whole-number Mid, so it can read Lockers[Mid].
Stage: Explain
The whole algorithm
Here is the whole search in Cambridge pseudocode. The array Lockers has already been filled with the fifteen numbers above, in order, so Lockers[1] is 3 and Lockers[15] is 77. The loop keeps going while the target has not been found and at least one position is still possible (Low <= High).
INPUT Target
Low ← 1
High ← 15
Found ← FALSE
WHILE Found = FALSE AND Low <= High DO
Mid ← DIV(Low + High, 2)
IF Lockers[Mid] = Target
THEN
Found ← TRUE
ELSE
IF Lockers[Mid] < Target
THEN
Low ← Mid + 1
ELSE
High ← Mid - 1
ENDIF
ENDIF
ENDWHILE
IF Found = TRUE
THEN
OUTPUT Target, " is at position ", Mid
ELSE
OUTPUT Target, " is not on the list"
ENDIFWhen the target is found, the loop stops straight away, so Mid still holds the position where it was found.
Follow the search for locker 47, one pass of the loop at a time.
Each step is one pass of the loop: find Mid, check the item there, then move Low or High, or stop.
Pass 1
Step 1 of 3: Low 1, High 15, Mid 8
Mid is DIV(16, 2) = 8. Lockers[8] is 35, which is smaller than 47, so Low becomes 9.
Technical detail: Positions 1 to 8 are thrown away. Seven positions, 9 to 15, are left.
Pass 2
Step 2 of 3: Low 9, High 15, Mid 12
Mid is DIV(24, 2) = 12. Lockers[12] is 58, which is bigger than 47, so High becomes 11.
Technical detail: Positions 12 to 15 are thrown away. Only 9, 10 and 11 are left.
Pass 3
Step 3 of 3: Low 9, High 11, Mid 10
Mid is DIV(20, 2) = 10. Lockers[10] is 47, which equals the target, so Found becomes TRUE and the loop stops.
Technical detail: The program outputs “47 is at position 10”. Only three items were looked at; a linear search would have looked at ten.
Check your understanding
Show the answer
Answer: B. Because 58 is bigger than 47, so 47 can only be before position 12.
When the middle item is too big, High moves to just before it: High ← Mid - 1.
Stage: Experiment
Trace it yourself
Fill in the trace table for the search for 47. The first row is given. Use the steps above to check yourself afterwards, not before.
| Pass | Low | High | Mid | Lockers[Mid] | Lockers[Mid] compared with 47 |
|---|---|---|---|---|---|
| 1 | 1 | 15 | 8 | 35 | smaller |
| 2 | 15 | ||||
| 3 |
Show the completed table
| Pass | Low | High | Mid | Lockers[Mid] | Lockers[Mid] compared with 47 |
|---|---|---|---|---|---|
| 1 | 1 | 15 | 8 | 35 | smaller |
| 2 | 9 | 15 | 12 | 58 | bigger |
| 3 | 9 | 11 | 10 | 47 | equal |
Three passes. The search stopped as soon as the item was found.
Now a harder trace, with no worked help after the first row. The caretaker asks for locker 50, which is not on the list. Work out what the search does, and when it decides to stop.
| Pass | Low | High | Mid | Lockers[Mid] | Lockers[Mid] compared with 50 |
|---|---|---|---|---|---|
| 1 | 1 | 15 | 8 | 35 | smaller |
| 2 | 15 | ||||
| 3 | |||||
| 4 | |||||
| End | 11 | 10 | - | - | Low is now bigger than High |
Show the completed table
| Pass | Low | High | Mid | Lockers[Mid] | Lockers[Mid] compared with 50 |
|---|---|---|---|---|---|
| 1 | 1 | 15 | 8 | 35 | smaller |
| 2 | 9 | 15 | 12 | 58 | bigger |
| 3 | 9 | 11 | 10 | 47 | smaller |
| 4 | 11 | 11 | 11 | 52 | bigger |
| End | 11 | 10 | - | - | Low is now bigger than High |
Four items were looked at. After pass 4, Low (11) is bigger than High (10): no position is left, so the loop ends and the program outputs “50 is not on the list”.
Check your understanding
Show the answer
Answer: D. Because Low is bigger than High, so there are no positions left that could hold 50.
A search that has ruled out every position stops and says “not found”. That is why the condition needs Low <= High as well as Found = FALSE.
Stage: Discover
How many checks, at most?
Every check throws away at least half of the positions that are left. That gives a way to count the most checks a search could need.
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?
- Hint 1: Take away the middle item, then split what is left into two equal halves.
- Hint 2: Keep going until one item is left.
Show a model answer
The middle item is checked, and 14 items are left in two halves of 7. After the first check at most 7 are still possible; after the second at most 3; after the third at most 1; and the fourth check looks at that last one. So at most 4 checks are needed for 15 items.
Working backwards gives the largest sorted list that can be searched with a given number of checks. One check handles one item. Each extra check adds a new middle item and doubles the part either side of it: two halves of the previous size, plus one.
| Checks allowed | Largest list that can be searched |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 |
Show the completed table
| Checks allowed | Largest list that can be searched |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
Each extra check roughly doubles the size of list that can be searched.
Check your understanding
Show the answer
Answer: B. 10, because 10 checks cover 1023 items, but 9 checks cover only 511.
Doubling the size of the list adds only one more check. That is why a binary search stays fast on very long lists.
Stage: Explain
Comparing two algorithms
For 100 items, 7 checks cover 127 items but 6 cover only 63, so a binary search needs at most 7 checks. A linear search might need up to 100. Here is the comparison, counting one check each time the program looks at an item in the list:
| Items in the sorted list | Linear search, at most | Binary search, at most |
|---|---|---|
| 15 | 15 | 4 |
| 100 | 100 | 7 |
| 1000 | 1000 | 10 |
| 1 000 000 | 1 000 000 | 20 |
Comparing algorithms for the same problem means choosing a fair measure, here the most items looked at, and reasoning from it. “Which is quicker?” has no single answer: it depends on what is known about the list.
Do not confuse: Linear search and binary search
- Does the list need to be sorted?Linear search
- No. It works on any list, because it only compares with each item in turn.A club list in the order the pupils joined.
- Does the list need to be sorted?Binary search
- Yes. Throwing away half the list is only safe when the list is in order.The locker list, smallest to largest.
- How many checks for 100 items, at most?Linear search
- Up to 100, one for each item.
- How many checks for 100 items, at most?Binary search
- At most 7, because each check halves what is left.
A binary search is not simply better: it needs the order, and a list that is not sorted must be sorted first.
“The middle” means the middle position, not the middle value. In a sorted list that begins 1, 2, 3, 100, 200, the middle item of the five is the third one, 3, even though 100 is nearer to the halfway point between 1 and 200. A binary search never looks at the values to decide where the middle is; it only uses DIV(Low + High, 2).
Also, a binary search is not always quicker. If the target happens to be the middle item, one check finds it, but if the target is the first item of a long list, a linear search finds it with one check, whereas a binary search needs several.
Apply it
Show the answer
Answer: B. Mostly correct: about 10 checks at most for 600 items, but a linear search can win on an early target.
Compare algorithms on the same measure and the same cases: the worst case shows that a binary search scales much better, even though a particular target can favour a linear search.
Stage: Apply
Spot the mistake
Sam (fictional) rewrites the update lines of the binary search like this. Everything else is the same.
IF Lockers[Mid] < Target
THEN
Low ← Mid
ELSE
High ← Mid - 1
ENDIFApply it
Show the answer
Answer: A. Low becomes 1 again, so Mid stays 1, and the loop repeats for ever.
The new Low or High must move past the item that has just been checked. If it does not, the search can look at the same item for ever.
Priya (fictional) runs the locker search on a list that nobody has sorted: 40, 10, 30, 20, 50, in positions 1 to 5, for the target 20.
Apply it
Show the answer
Answer: A. “20 is not on the list”, even though 20 is there, because the order broke the search.
A binary search on an unsorted list can throw away the very half that holds the target, and then report that it is not there.
Stage: Apply
Counting the checks in code
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.
Work this out on paper or the board first. Nothing here is marked: compare yours with the model answer.
- Hint 1: A counter goes up by one every time an item is looked at. Which line looks at an item?
- Hint 2: Set the counter to 0 before the loop starts.
Show a model answer
INPUT Target
Low ← 1
High ← 15
Found ← FALSE
Checked ← 0
WHILE Found = FALSE AND Low <= High DO
Mid ← DIV(Low + High, 2)
Checked ← Checked + 1
IF Lockers[Mid] = Target
THEN
Found ← TRUE
ELSE
IF Lockers[Mid] < Target
THEN
Low ← Mid + 1
ELSE
High ← Mid - 1
ENDIF
ENDIF
ENDWHILE
IF Found = TRUE
THEN
OUTPUT Target, " is at position ", Mid
ELSE
OUTPUT Target, " is not on the list"
ENDIF
OUTPUT "Items looked at: ", CheckedChecked starts at 0 and goes up by 1 on each pass, straight after Mid is worked out. For 47 the loop runs three times, so it outputs 47 is at position 10 and Items looked at: 3. For 50 it runs four times, so it outputs 50 is not on the list and Items looked at: 4, as the two traces showed.
Go deeper The same binary search in Python
lockers = [3, 8, 12, 17, 21, 26, 30, 35, 41, 47, 52, 58, 63, 70, 77]
target = 47
low = 0
high = len(lockers) - 1
found = False
checked = 0
while not found and low <= high:
mid = (low + high) // 2
checked = checked + 1
if lockers[mid] == target:
found = True
elif lockers[mid] < target:
low = mid + 1
else:
high = mid - 1
if found:
print(target, "is at position", mid + 1)
else:
print(target, "is not on the list")
print("Items looked at:", checked)- Python counts positions from 0, so
lowstarts at 0 andhighatlen(lockers) - 1; the position is shown asmid + 1to match the pseudocode.//is Python’s DIV. Lesson 18 introduces the language. - This program prints
47 is at position 10andItems looked at: 3. Changingtargetto 50 prints50 is not on the listandItems looked at: 4. - Python also has built-in ways to search, such as the
bisectmodule. Writing the algorithm out shows what they do.
Stage: Consolidate
Show what you know
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.
Show a model answer
A good answer says that a binary search checks the middle item, uses the fact that the list is sorted to decide which half the target can be in, throws the other half away, and repeats on what is left until it finds the item or nothing is left. Each check halves the list, so doubling the length of the list adds only one more check: 100 items need at most 7, where a linear search might need 100. It only works because the list is in order.
Apply it
Show the answer
Answer: C. A binary search, because the list stays sorted, so each look-up needs only a few checks.
When a list is already sorted and searched often, a binary search wins. If a list is searched once and is not sorted, putting it in order first may cost more than a linear search.
Think it through
Which part of this lesson are you least sure about? Write one question you would ask your teacher.
Show a model answer
There is no wrong answer. Two questions worth asking: “how do I decide whether to use Mid - 1 or Mid + 1?” (move past the item just checked) and “what if the list has an even number of items?” (DIV still gives a whole number, so the search still works).
- A binary search finds an item in a sorted list by checking the middle item, throwing away the half that cannot hold the target, and repeating on the half that is left.
- The middle position is
Mid ← DIV(Low + High, 2). IfLockers[Mid]is smaller than the target,Low ← Mid + 1; if bigger,High ← Mid - 1; if equal, the item is found. The loop ends when it is found or whenLowbecomes bigger thanHigh. - A list of 100 items needs at most 7 checks, 1000 items at most 10, and a million at most 20: each doubling of the list adds one check. A linear search might need to look at every item.
- The list must be in order. On an unsorted list a binary search can discard the half that holds the target and report that it is missing.
- Usual faults:
Low ← Midinstead ofMid + 1, a loop that never ends, thinking “middle” means middle value, and using the search on an unsorted list.
Sources and scope
- What this lesson is. The seventeenth lesson of the Algorithms and Programming module, written for this site. It teaches binary search, the second searching algorithm after Lesson 11, and compares the two by counting checks. Its curriculum links are provisional and imply no review or endorsement by any examination board, and they were written against the published Key Stage 3 programme of study, Cambridge IGCSE Computer Science 0478 and Cambridge International AS & A Level Computer Science 9618.
- Original material. The guessing game, the school lockers, the pupil numbers, the shop and Sam and Priya are fictional, written for this lesson. Every trace was worked out by hand and checked with an equivalent Python program, which also confirmed the greatest number of items looked at for a list of 15, 100 and 1000 items.
- Simplified on purpose. The comparison counts only the items a program looks at, and ignores the other work in the loop. Lists are short, numeric and have no repeated items. The lesson does not name Big O notation or the cost formula; it shows the doubling pattern only. A binary search for the first of several equal items, and searching with recursion, are not taught.
- Left to later lessons. Sorting other than bubble sort (Lesson 11), and measuring how fast an algorithm grows in general.
A sequence of precise steps that solves a problem or completes a task.
The number system with only two digits, 0 and 1, in which each column is worth twice the column to its right.
A search of a sorted list that checks the middle item and, by seeing whether the target is bigger or smaller, throws away half of the list each time.
A sort that passes along a list again and again, comparing neighbouring items and swapping any that are the wrong way round, until the list is in order.
A search that checks the items of a list one at a time, from the first, until it finds the target or reaches the end.
A precise but language-independent way of writing an algorithm, with set keywords such as IF, WHILE and OUTPUT, that is not tied to any one programming language.
A high-level programming language written as text, popular for learning and for real work, in which indentation shows which lines belong together.
A table used to follow an algorithm by hand, with a column for each variable and for the output and a row for each step, to record how the values change.
Your progress on this lesson
Saved in this browser only. It is not sent anywhere, does not follow you to another device, and is lost if you clear this site’s data.
This browser is not allowing the site to save progress, so it will be forgotten when you leave the page.