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.
Code a linear search in Python
PracticalPresent ▶
What this lesson covers
Topic 12 Searching and sorting
KS3 Computing · Searching finds an item. Sorting puts items in order. Some algorithms are hugely faster than others on big lists, and the difference grows as the list grows.
Topic 13 Programming basics
KS3 Computing · A program stores information in variables, works on it with operators, and controls the order with sequence, selection and iteration. Examples are in Python, with Scratch alongside for Year 7.
Programming Computational ThinkingCambridge Lower Secondary Computing 0860
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.
Success criteria
- 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.
Key words
Say each word, then read what it means. Every one is in the glossary too.
- 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.
- 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").
- 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.
- Infinite loop
- A loop whose condition never becomes false.
The explanation
Read it here, or open the study page below to go one step at a time with things to try.
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.
| 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.)
Scratch → Python
| Scratch | Python |
|---|---|
| say [Hello] | print("Hello") |
| ask [Name?] and wait | name = input("Name? ") |
| set [score] to 0 | score = 0 |
| change [score] by 1 | score = score + 1 |
| if … then … else | if …: / else: |
| repeat 10 | for i in range(10): |
| repeat until … | while not …: |
| forever | while True: |
| pick random 1 to 10 | random.randint(1, 10) |
Study it
Open the study page and go one step at a time.
Topic 12 · Year 8
Searching and sorting
Searching finds an item. Sorting puts items in order. Some algorithms are hugely faster than others on big lists.
Topic 13 · Year 8Programming basics
A program stores information in variables, works on it with operators, and controls the order with sequence, selection and iteration. Examples are in Python.
Check yourself
One question at a time. The reason shows after each answer.
Saved on this device.