GCSE · Computer Science · Edexcel · Spec 1CP2

Binary search

Find one item among 1,000 in at most ten comparisons. That's the trick binary search pulls off.

Computer Science · Searching

Watch the list shrink

You already know this trick. Guess a number from 1 to 15 by always going for the middle, and you'll never need more than four guesses. Binary search uses the same idea on a list. Step through the search for flute and watch the range get smaller.

Before each step, predict: which item is the midpoint, and which half survives?

 1  take the ordered list and the search item
 2  range = the whole list
 3  midpoint = the item in the middle of the range
 4  compare the midpoint with the search item
 5  if midpoint < search item: range = the items after the midpoint
 6  if midpoint > search item: range = the items before the midpoint
 7  if midpoint = search item: stop, the item is found
 8  repeat from line 3 on the new range
 9  if the range runs out: report 'not found'

Variables

list=banjo, cello, drums, flute, guitar, harp, oboe, piano, violinsearch for=flute

Output

Step 1: The list is in alphabetical order, so it is ordered. That's the whole reason the next trick works. We're hunting for flute.

1 / 10

Use Next and Back to move through the search. The range is where flute could still be; everything in 'ruled out' is gone for good.

Step 1 of 10: The list is in alphabetical order, so it is ordered. That's the whole reason the next trick works. We're hunting for flute..

When can you use it?

The shuffled playlist

Your friend has 500 songs in a shuffled, random order and wants to find one particular song as fast as possible.

Which is closest to what you think right now?

Binary search will find it fastest. It works on any list.It can't be searched at all. Searching needs the songs to be in order.Binary search won't work on it as it is. Use a linear search, or sort the songs first and then use binary search.Binary search will work, as long as you always take the middle-left song.

How sure are you?

I'm sureI think soI'm guessing

Binary search will find it fastest. It works on any list.

This is a common misconception

Not here. Binary search decides which half to keep from the midpoint: 'my song comes after this one, so it must be in the later half.' That's only true if the list is in order. In a shuffled list the song could be sitting in the half you just threw away, so binary search can miss a song that is really there.

It can't be searched at all. Searching needs the songs to be in order.

This is a common misconception

Searching still works, just not binary search. A linear search checks the songs one at a time, and that doesn't care about order. Or sort the songs first, and then binary search is back on.

Binary search won't work on it as it is. Use a linear search, or sort the songs first and then use binary search.

This matches the evidence

Exactly right. Binary search needs ordered data, because the midpoint comparison is what tells it which side the song must be on. With no order there's no clue, so either check each song in turn or sort first.

Binary search will work, as long as you always take the middle-left song.

This is a common misconception

The middle-left rule only decides which item is the midpoint when the range has an even number of items. It doesn't fix the real problem: in a shuffled list, comparing with the midpoint still tells you nothing about which half the song is in.

Binary search needs ordered data. No order? Use a linear search, or sort the data first and then binary search.

Your turn

Search for trumpet

Use binary search to look for trumpet in the same ordered list: banjo, cello, drums, flute, guitar, harp, oboe, piano, violin. The first step is done for you. Choose each missing step.

Range: all 9 items. The midpoint is guitar, the 5th item. Trumpet comes after guitar, so keep the items after it: harp, oboe, piano, violin.
missing step

Which line is step 2?

Range: harp, oboe, piano, violin. That's 4 items, so the midpoint is the middle-left item: oboe.Range: harp, oboe, piano, violin. That's 4 items, so the midpoint is the middle-right item: piano.Range: guitar, harp, oboe, piano, violin. That's 5 items, so the midpoint is the 3rd item: oboe.

How fast is it?

1,000 items. How many comparisons?

An ordered list holds 1,000 items. What is the MOST comparisons a binary search could need to find one item?

Your estimate

501 comparisons

An ordered list holds 1,000 items. What is the MOST comparisons a binary search could need to find one item? Estimate between 1 comparisons and 1000 comparisons.

1 comparisons1000 comparisons

Say it in your own words

Why is binary search quicker?

Explain why a binary search is usually quicker than a linear search on a large, ordered list. [3 marks]

Your answer

0 words · your answer stays on this page and is not sent anywhere.

The mark scheme

Each comparison with the midpoint discards half of the remaining items (the data is halved every time). (1 mark)
So it needs far fewer comparisons than a linear search, which may check the items one at a time (e.g. at most 10 comparisons for 1,000 items). (1 mark)
Half can be discarded safely because the list is ordered, so the midpoint comparison shows which side the item must be on. (1 mark)

Model answer

Every time binary search compares the midpoint with the search item, it throws away half of the items that are left, so the range shrinks very quickly. That means it needs far fewer comparisons than a linear search, which may have to check the items one at a time: 1,000 items need at most 10 comparisons. It can throw half away safely because the list is ordered, so the midpoint shows which side the item must be on.

Halves every time, so far fewer comparisons, and that only works because the data is ordered.

WHAT YOU'VE LEARNED

A quick recap of today's lesson.

Check the middle, throw away half, repeat.

What you need to know

Binary search only works on ordered data: items in ascending or descending order.
Each round: find the midpoint item of the range, compare it with the search item, then keep only the half that could still hold it.
If the range has an even number of items, the midpoint is the middle-left item; if only one item is left, that item is the midpoint.
The search stops when the midpoint matches the search item, or reports 'not found' when the range runs out.

The big picture

Binary search finds an item in an ordered list by checking the item in the middle and throwing away the half that can't contain what you're looking for. It repeats on the half that's left until it finds a match, or until nothing is left, which means the item isn't there. It only works on ordered data; for unordered data, use a linear search or sort the data first. Because every comparison halves the data, it is very fast: 1,000 items need at most 10 comparisons.

Key points

1An ordered list has its values in ascending or descending order.

2Midpoint less than the search item: keep the items after it. Midpoint greater: keep the items before it.

3Every comparison discards half of the remaining data.

4Best case: 1 comparison, when the item is the first midpoint. A list of 9 items needs at most 4.

51,000 items need at most 10 comparisons, and doubling to 2,000 adds at most one more.

.we-_R_18slubsnpfiv5ubrb_ [data-we-step]{display:flex !important}.we-_R_18slubsnpfiv5ubrb_ [data-we-solution]{display:block !important}.we-_R_18slubsnpfiv5ubrb_ [data-we-reveal]{display:none !important}

Worked example

Problem

Use a binary search to find 30 in the ordered list 3, 8, 12, 17, 21, 26, 30, 35, 41, 47. Show each midpoint and which part of the list is kept.

⚠ Watch out

Putting the midpoint back into the new range. Once it has been compared and isn't a match, it's out: the new range is only the items before it or after it.

🧠

Memory hook

Middle. Compare. Bin half. Repeat. It's like hunting for a word in a dictionary: open it in the middle, decide which side your word is on, and never look at the other half again.

✓

Check yourself

A list of 9 items needs at most 4 comparisons. Without tracing anything, what is the most a list of 18 items could need, and why?

Flashcards

(14)

What does a binary search do?

It searches for an item in an ordered (sorted) data set by repeatedly comparing the middle item of the range with the search item.

What is an ordered list?

A list whose values are in ascending or descending order.

Why does binary search only work on ordered data?

It works out where the search item should be from the value at the midpoint. Without order, that comparison can't tell you which side the item is on.

The data isn't in order. What are your two options?

Use a linear search, or sort the data first and then use a binary search.

In a binary search, what is the 'range'?

The items where the search item might still be. It starts as the whole list and is given by the indices of its first and last items.

The midpoint item is LESS than the search item. What is the new range?

The items after the midpoint.

The midpoint item is GREATER than the search item. What is the new range?

The items before the midpoint.

How do you pick the midpoint when a range holds an even count, such as 4 or 6?

Take the middle-left one: the 2nd of 4, or the 3rd of 6.

Only one item is left in the range. Which is the midpoint?

That one item.

What are the two ways a binary search can end?

The midpoint equals the search item (found), or the range runs out with no match (report 'not found').

How much of the remaining data does each comparison discard?

Half of it.

What is the best case for a binary search?

The search item is the first midpoint, so it needs just one comparison.

Most comparisons needed for a list of 1,000 items?

10.

The list doubles from 1,000 to 2,000 items. What happens to the most comparisons needed?

It goes up by at most one.

Tap any card to flip it, or use Study as deck to go through them one at a time. In the full lesson these run as a spaced-repetition deck — you rate each card Hard, Good or Easy and the tricky ones keep coming back until they stick.

Learning with Lightbulb is opening soon

You can use this lesson now. Join the waitlist and we'll let you know when the full Lightbulb experience is ready.

Keep me posted

Watch the list shrink

The shuffled playlist

Search for trumpet

1,000 items. How many comparisons?

Why is binary search quicker?

More Edexcel GCSE Computer Science topics