Linear vs binary search with numbered cards

UnpluggedTopic 12 Searching and sorting

Year 8 · Algorithms: search and sort · Lesson 1 of 5

You will learn to

Carry out a linear search on cards, checking each one in turn.
Carry out a binary search on sorted cards: check the middle, then throw away half.
Explain why binary search only works on a sorted list.
Compare the checks each search needs, using the binary search toy.

Year 8 · Algorithms: search and sort · Lesson 1 of 5

Success criteria

You have got it when you can say:

I can find 17 in twenty sorted cards both ways, and count my checks.
I can explain why binary search needs at most 5 checks for 20 cards.
I can choose the right search for a sorted list and for an unsorted list.

Year 8 · Algorithms: search and sort · Lesson 1 of 5

Retrieval starter

Questions from before. Write your answers, then show them.

Last unit
x = input("Number: ") and the user types 5. What type is x?

A intB floatC str

C. str
Last unit
What does 17 % 5 give?

A 3.4B 3C 2

C. 2
Earlier this year
A '1 TB' drive shows 931 GB in Windows because…

A Some space is brokenB The drive is fakeC Windows divides by 1,024 but still writes GB

C. Windows divides by 1,024 but still writes GB

Year 8 · Algorithms: search and sort · Lesson 1 of 5

Key words (1 of 2)

Linear search: Check every item in turn.
Binary search: Search a sorted list by halving it each step.
Bubble sort: Swap neighbours until a whole pass makes no swaps.
Insertion sort: Slide each item into its place in the sorted part.

Year 8 · Algorithms: search and sort · Lesson 1 of 5

Key words (2 of 2)

Merge sort: Split into single items, then merge back in order.

The explanation · step 1 of 2

Linear search

Linear search: check every item from the start until you find it.

Works on any list, sorted or not.
Simple.
Slow on long lists: a million items may need a million checks.

The explanation · step 2 of 2 · part 1 of 2

Binary search

Binary search needs a sorted list. Like a dictionary: open in the middle, throw away the wrong half, repeat.

Look at the middle item.
Is it the one? Stop.
Is your item bigger? Throw away the left half. Smaller? Throw away the right half.
Repeat with what's left.

The explanation · step 2 of 2 · part 2 of 2

Binary search (continued)

Items	Linear (worst)	Binary (worst)
10	10	4
1,000	1,000	10
1,000,000	1,000,000	20

?Why?

Why so fast? Each check halves the list. Doubling the list only adds one check. (2¹⁰ = 1,024 and 2²⁰ ≈ 1 million.)

The explanation · step 2 of 2

The maths: Most checks binary search can need

Year 8 · Algorithms: search and sort · Lesson 1 of 5

Try it: Binary search, step by step

Year 8 · Algorithms: search and sort · Lesson 1 of 5

Quick quiz · 1 of 3

Binary search only works if the list is…

A Made of numbers
B Short
C Sorted

C. Sorted

Throwing away half only makes sense if the list is in order. Sorted words work too.

Year 8 · Algorithms: search and sort · Lesson 1 of 5

Quick quiz · 2 of 3

What is the most checks binary search can need on 1,000 sorted items?

A 1,000
B 10
C 500

B. 10

1,000 halves 9 times to reach 1 (2⁹ = 512), plus one last check: 9 + 1 = 10.

Year 8 · Algorithms: search and sort · Lesson 1 of 5

Quick quiz · 3 of 3

A linear search on 50 unsorted items, looking for something that is not there, makes…

A 25 checks
B 50 checks
C 1 check

B. 50 checks

It can only say 'not found' after checking every item: the worst case, n = 50.

Year 8 · Algorithms: search and sort · Lesson 1 of 5

Exit ticket

Answer on paper before you go. Then check.

Bubble sort compares…

A Random pairsB NeighboursC The first and last items

B. Neighbours Items next to each other, swapping them if they're in the wrong order.
During bubble sort, a whole pass makes no swaps. This means…

A Start again from the beginningB The list is sorted: stopC Do one more pass to be safe

B. The list is sorted: stop No pair was out of order, so the whole list is in order. This is the early stop.