In simple terms
A friendly intro before the formal notes — no formulas yet.
Computer Recipes: Searching and Sorting
Algorithms are just step-by-step instructions for solving a problem, like a recipe for a computer. We'll look at common recipes for finding items in a list (searching) and putting a list in order (sorting).
Imagine finding a specific book in a library. You could start at the first shelf and check every single book until you find it (Linear Search). A much faster way is to use the library's catalogue to find the correct section, then go to the middle of that section and decide whether to look in the first or second half, repeating this until you find the book (Binary Search). Before you can do that, someone had to put all the books in order (Sorting), perhaps by repeatedly swapping pairs of out-of-order books on a cart (Bubble Sort).
- 1
Linear search: check each item in order.
- 2
Binary search: halve sorted list each step.
- 3
Bubble sort: compare adjacent pairs.
- 4
Trace table for given algorithm input.
Explore the concept
Use the live diagram and synced steps — play it or tap a step card to walk through.
Full topic notes
Formal explanation with the rigour you need for the exam.
Searching Algorithms
Searching is the process of finding a specific item, or 'key', within a collection of items, such as an array or a list. The success of a search is determined by whether the key is found. The efficiency of a search is measured by how many comparisons it needs to make in the worst case.
1. Linear Search
The Linear Search is the most straightforward search algorithm. It begins at the first element of a data structure and checks each element in sequence until the desired element is found or the end of the structure is reached. It's simple to implement but can be very slow on large datasets.
Advantage: Works on any list, sorted or unsorted.
Advantage: Simple to understand and implement.
Disadvantage: Inefficient for large lists. The time taken grows linearly with the number of items ().
2. Binary Search
The Binary Search is a much more efficient 'divide and conquer' algorithm. It requires the list to be sorted. The algorithm compares the search key with the middle element of the list. If the key is smaller, it repeats the search on the lower half of the list; if larger, it searches the upper half. This process is repeated, halving the search space with each comparison.
Pre-condition: The list MUST be sorted.
Advantage: Extremely fast for large, sorted lists, with a time complexity of .
Disadvantage: Requires a sorted list. The overhead of sorting an unsorted list first might make it slower than a linear search for a single search operation.
Sorting Algorithms
Sorting arranges items in a list into a specific order, typically numerical or alphabetical. While many sophisticated sorting algorithms exist, Bubble Sort is a fundamental one you need to know for its simplicity, even though it's not very efficient.
1. Bubble Sort
Bubble Sort works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. This process is repeated until no swaps are needed, which indicates that the list is sorted. In each pass, the largest unsorted element 'bubbles' up to its correct final position.
Tracing Algorithms
A trace table is a crucial tool for understanding and debugging algorithms. In Paper 4, you will frequently be asked to 'dry run' a piece of pseudocode and complete a trace table for a given set of input data. This involves meticulously tracking the value of each variable line by line or after each loop iteration.
When completing a trace table in an exam, be methodical. Use a pencil and ruler to keep your columns aligned. Write down the value of a variable in a new row every time it changes. If a variable doesn't change during a step, you may be required to copy its previous value into the new row – read the question carefully!
Worked examples
See the formulas applied — reveal one step at a time, like the exam.
An integer array Data is sorted in ascending order: [3, 5, 8, 11, 15, 22, 29, 31]. Trace the execution of a binary search to find the value 22. The array has indices 0 to 7. Use Low, High, and (integer division).
- 1
Target Value: 22 Initial state: ,
Trace the Bubble Sort algorithm on the array [7, 2, 8, 5]. Show the state of the array after each complete pass.
- 1
Initial Array: [7, 2, 8, 5]
How it all connects
The big idea sits in the middle — tap a linked idea to explore the link.
Tap a linked idea to see how it connects back to the main topic — that connection is what examiners reward.
Glossary
Try to recall each definition before you reveal it.
Quick check
Answer in your head first — then tap to check. No pressure.
Revision flashcards
Flip the card. Test yourself before the exam.
What is an algorithm?
A finite, well-defined sequence of steps or rules to solve a specific problem or perform a computation. It must be unambiguous and guaranteed to terminate.
Key takeaways
Review these before you close the topic — retrieval beats re-reading.
- ✓
Advantage: Works on any list, sorted or unsorted.
- ✓
Advantage: Simple to understand and implement.
- ✓
Disadvantage: Inefficient for large lists. The time taken grows linearly with the number of items ().
Practice — then mark it
The whole point: a real Cambridge question, marked mark-by-mark.
Practice Algorithm Problems
Practice Algorithm Problems
Extra simulations & links
PhET, GeoGebra and other curated tools — open in a new tab.
Frequently asked
Checkpoint
One marked question is worth ten re-reads — close the loop before you move on.
Reading it isn’t knowing it — prove it.
Before you move on: do Practice Algorithm Problems on paper, snap a photo, and get examiner-style feedback on exactly where you win and lose marks.