Year 8 · Summer 1

Algorithms: search and sort · Lesson 5 of 5

Code a linear search in Python

PracticalTopic 12 Searching and sortingTopic 13 Programming basics

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

You will learn to

  • Use a Python list to store many names under one variable name.
  • Use a for loop and an if to check each item in turn.
  • Create a linear search that prints 'Found' or 'Not found'.
  • Explain why 'Not found' can only be decided after the loop has checked every item.

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

Success criteria

You have got it when you can say:

  • I can write a linear search that finds a name in a list.
  • I can make my program say 'Not found' only once, at the end.
  • I can count the checks and print how many there were.

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

Retrieval starter

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

  1. Last lesson

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

    A 50 checksB 25 checksC 1 check

    A. 50 checks

  2. Last unit

    count = 5, then while count > 0: print(count). What happens?

    A Prints 5 for everB Prints nothingC Prints 5 4 3 2 1

    A. Prints 5 for ever

  3. Earlier this year

    How many rows in a truth table with 3 inputs?

    A 8B 6C 3

    A. 8

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

Key words (1 of 4)

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 5 of 5

Key words (2 of 4)

Merge sort
Split into single items, then merge back in order.
Variable
A named place in memory that holds a value.
Assignment
Storing a value in a variable. = in Python, ← in pseudocode.
Casting
Changing a value from one data type to another, like int("13").

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

Key words (3 of 4)

Concatenation
Joining strings together: "7" + "7" = "77".
Selection
Choosing a path with if / else.
Iteration
Repeating steps: a loop.
Boolean
A value that is only True or False.

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

Key words (4 of 4)

Infinite loop
A loop whose condition never becomes false.

The explanation · step 1 of 3

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 3 · 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.

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

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

Binary search (continued)

ItemsLinear (worst)Binary (worst)
10104
1,0001,00010
1,000,0001,000,00020
?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 3

The maths: Most checks binary search can need

The explanation · step 3 of 3

Scratch → Python

ScratchPython
say [Hello]print("Hello")
ask [Name?] and waitname = input("Name? ")
set [score] to 0score = 0
change [score] by 1score = score + 1
if … then … elseif …: / else:
repeat 10for i in range(10):
repeat until …while not …:
foreverwhile True:
pick random 1 to 10random.randint(1, 10)

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

Quick quiz · 1 of 3

During bubble sort, a whole pass makes no swaps. This means…

  1. A Start again from the beginning
  2. B Do one more pass to be safe
  3. C The list is sorted: stop

C. The list is sorted: stop

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

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

Quick quiz · 2 of 3

Which sort splits the list into single items first?

  1. A Bubble sort
  2. B Merge sort
  3. C Insertion sort

B. Merge sort

Split until every piece has 1 item, then merge back in order.

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

Quick quiz · 3 of 3

Insertion sort is especially quick when the list is…

  1. A Nearly sorted
  2. B In reverse order
  3. C Very long

A. Nearly sorted

Each item only slides as far as it needs. Nearly sorted means hardly any shifting.

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

Exit ticket

Answer on paper before you go. Then check.

  1. Merge sort is fast on big lists. What's its main cost?

    A It needs the list to be sorted firstB It needs extra memory for the merged copiesC It only works on numbers

    B. It needs extra memory for the merged copies Merging builds new lists, so it uses about another n spaces of memory.

  2. What does print("3" + "4") show?

    A 7B An errorC 34

    C. 34 They're strings, so + joins them: 34.

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

Homework and the challenge

Homework

Study page 12 to the quiz; practice 'Merge two lists'.

End-of-unit challenge

Trace each sort on a short list, then justify which algorithm suits a given scenario.