Searching algorithms — AQA GCSE Computer Science
Linear and binary searches are fundamental algorithms used to locate specific data items within a dataset. While a linear search checks elements sequentially and operates on unsorted lists, a binary search requires pre-sorted data to repeatedly halve the search space for superior efficiency.
Searching algorithms explained
A comparison must show how each search works before judging it.
Read the full explanation
Linear search starts at the first item and checks each item in turn until the target is found or the list ends; it works on unordered data and on small lists, but may examine every item, so time grows in proportion to list size. Binary search needs the data sorted; it examines the middle item, then discards the half that cannot contain the target and repeats on the remaining half, so each step roughly halves the search space. Contrast the requirements (sorted versus any order), the mechanics (sequential checking versus repeated halving), and the consequences for efficiency on large data. A worked example on a sorted list of numbers, naming the middle item checked at each stage, makes the contrast concrete.
Your focus
- Describe step by step how linear search and binary search each locate a target.
- Explain the data requirements and efficiency consequences of each algorithm.
- Apply both algorithms to a given list and compare the items examined.
Which command word is this?
Identify both similarities and differences between linear and binary search (e.g., prerequisites, comparison counts, performance with large datasets).
Searching algorithms exam tips
Topic Overview
Searching algorithms are systematic procedures designed to locate a specific target value within a collection of data, such as an array or list. In AQA GCSE Computer Science, students are required to understand, trace, compare, and implement two foundational algorithms: linear search and binary search.
Mastering these algorithms develops algorithmic thinking and provides a practical foundation for understanding computational efficiency. These principles link directly to Paper 1 topics, including sorting algorithms, data structures, and computational complexity.
Key Concepts
- →Linear Search: Starts at the first element (index 0) and inspects every item sequentially until the target is found or the end of the list is reached. Operates on both unsorted and sorted datasets.
- →Binary Search: An efficient 'divide-and-conquer' algorithm that checks the middle item of a sorted list, discarding the non-viable half with each comparison. Strictly requires sorted data.
- →Algorithmic Efficiency: The measure of steps required relative to dataset size (n). Linear search grows proportionally (worst case n comparisons), whereas binary search grows logarithmically (worst case log2(n) + 1 comparisons).
- →Boundary Pointers: Binary search relies on maintaining and adjusting 'low', 'high', and 'mid' index pointers, using integer division (DIV) to determine the middle position.
Marking Points
- Describes linear search as checking items one at a time from the start until the target is found or the list is exhausted.
- Describes binary search as examining the middle item and repeatedly discarding the half that cannot contain the target.
- States that binary search requires the data to be sorted, whereas linear search works on unordered data.
- Explains that binary search is generally more efficient on large sorted data sets because the search space halves each step, while linear search may need to check every item.
- Notes that linear search can be preferable for small or unsorted lists, or where sorting would cost more than searching.
- Supports the comparison with a worked example on a specific list, identifying the items examined in each algorithm.
Examiner Tips
- 💡Structure the answer around clear comparison points: data requirement, method, and efficiency.
- 💡Use a short worked example with a named list to show the items each algorithm examines.
- 💡Link efficiency claims to list size and to whether sorting is needed, rather than asserting one is simply better.
- 💡Always check whether the list provided in the exam prompt is sorted before recommending or writing a binary search algorithm.
- 💡In trace tables, show the integer division clearly: write down `mid = (low + high) DIV 2` and state the resulting whole number index without rounding up or adding decimals.
- 💡When explaining efficiency, avoid vague terms like 'quicker' or 'easier'—use precise examiner terminology such as 'fewer comparisons' or 'logarithmic reduction of search space'.
Common Mistakes
- Claiming binary search works on any list: correct this by stating the data must be sorted first.
- Saying binary search always checks every item: correct this by explaining it halves the remaining search space each step.
- Treating linear search as always worse: correct this by noting it suits small or unsorted data and needs no sorting.
- Describing binary search as starting at the middle of the whole list every time without narrowing: correct this by showing the search range shrinks after each comparison.
- Believing binary search can run on any list: Students often forget that binary search fails completely if data is not pre-sorted in ascending or descending order.
- Assuming linear search is always slower: If the target element happens to be at the very start of the list (index 0), linear search finds it in 1 comparison, matching the best case of binary search.
- Confusing array index with array value: Students frequently use values instead of positions when computing the middle pointer `(low + high) DIV 2`.
Revision Plan
- 1Day 1-2: Write out and trace the linear search algorithm by hand on paper with small arrays, ensuring you understand the loop termination condition.
- 2Day 3-5: Practice the binary search algorithm, focusing on updating low and high pointers using DIV; trace at least three exam examples with odd and even length lists.
- 3Day 6-7: Complete comparison questions assessing worst-case, best-case, and average-case comparisons for varying list sizes.
- 4Day 8-10: Work through past paper questions from AQA Paper 1, timing yourself and practicing writing algorithms in AQA Pseudocode or Python.
Exam Question Types
- 📋Trace Table Questions: Completing a table with columns for low, high, mid, and list[mid] to demonstrate how an algorithm locates an item or concludes it is absent.
- 📋Algorithm Evaluation / Comparison: 2 to 4 mark questions asking you to compare the suitability of linear vs binary search for a specific scenario.
- 📋Pseudocode / Code Completion: Writing or filling in missing lines of code for a search function using standard AQA programmatic syntax.
Command Word Expectations (AQA)
Identify both similarities and differences between linear and binary search (e.g., prerequisites, comparison counts, performance with large datasets).
Provide a step-by-step account of the algorithm's process without necessarily writing code, mentioning pointers, halving the list, or sequential checks.
Give a concise, single-word or short-phrase response with no detailed explanation required (e.g., stating the maximum comparisons needed).
How Students Lose Marks (Examiner Pitfalls)
Step-by-Step Worked Solutions
Question: An array contains the following sorted numbers: [4, 9, 15, 23, 38, 42, 56, 71, 89]. Using a binary search, show the steps taken to search for the value 42. Clearly show the low, high, and middle positions for each comparison.
- 1.Step 1: Identify indices and starting pointers: Array length is 9 (indices 0 to 8). Set low = 0 and high = 8.
- 2.Step 2: Iteration 1: Calculate mid = (0 + 8) DIV 2 = 4. The value at index 4 is 38. Compare 42 to 38: 42 is greater than 38, so set low = mid + 1 = 5.
- 3.Step 3: Iteration 2: Current search range is low = 5, high = 8. Calculate mid = (5 + 8) DIV 2 = 13 DIV 2 = 6. The value at index 6 is 56. Compare 42 to 56: 42 is less than 56, so set high = mid - 1 = 5.
- 4.Step 4: Iteration 3: Current search range is low = 5, high = 5. Calculate mid = (5 + 5) DIV 2 = 5. The value at index 5 is 42. Compare 42 to 42: A match is found at index 5.
Question: A dataset contains 128 sorted elements. State the maximum number of comparisons needed to find an item or confirm it is not present using (i) a linear search, and (ii) a binary search.
- 1.Step 1: In a linear search, every element is checked one by one. In the worst-case scenario (item at the end or not present), it must check all n elements. For n = 128, maximum comparisons = 128.
- 2.Step 2: In a binary search, the dataset is halved with each comparison. The maximum number of comparisons is equal to ceil(log2(n + 1)) or repeatedly dividing: 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1, which represents 8 comparisons (log2(128) + 1 = 7 + 1 = 8 comparisons to confirm absence).
- 3.Step 3: State both comparative figures clearly.