Skip to topic
    ← Back to course topics

    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

    1. Describe step by step how linear search and binary search each locate a target.
    2. Explain the data requirements and efficiency consequences of each algorithm.
    3. 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
    1. 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.
    2. 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.
    3. 3Day 6-7: Complete comparison questions assessing worst-case, best-case, and average-case comparisons for varying list sizes.
    4. 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)
    Compare

    Identify both similarities and differences between linear and binary search (e.g., prerequisites, comparison counts, performance with large datasets).

    Describe

    Provide a step-by-step account of the algorithm's process without necessarily writing code, mentioning pointers, halving the list, or sequential checks.

    State

    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)
    Pitfall: Stating that binary search is always faster than linear search without considering list state or list size.
    ❌ Weak Answer (Loses Marks):Binary search is always better because it finds the item much quicker than linear search.
    Example improved answer:Binary search is significantly more efficient for large datasets because its search space halves with each step. However, it requires the list to be in sorted order first. For a small or unsorted dataset, linear search may be preferred because sorting an unsorted list introduces additional computational overhead. In the best-case scenario where the target is at index 0, linear search completes in a single comparison.
    Examiner Tip: Always specify that binary search strictly requires the dataset to be ordered, and mention that sorting an unsorted list first can take more time than running a simple linear search.
    Pitfall: Calculating the midpoint incorrectly or forgetting to update the pointers to exclude the midpoint on subsequent iterations.
    ❌ Weak Answer (Loses Marks):The midpoint is found by dividing by 2, and then you check either the left or right side including the middle item again.
    Example improved answer:Calculate the midpoint using integer division: mid = (low + high) DIV 2. If target is less than list[mid], update high = mid - 1. If target is greater than list[mid], update low = mid + 1. The midpoint must be excluded from the new search boundary because it has already been evaluated.
    Examiner Tip: When tracing binary searches in an AQA exam, explicitly show the low, high, and mid index values at each iteration, and remember to use mid - 1 or mid + 1 when updating boundaries.
    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. 1.Step 1: Identify indices and starting pointers: Array length is 9 (indices 0 to 8). Set low = 0 and high = 8.
    2. 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. 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. 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.
    Final Answer: The item 42 was found at index 5 after 3 comparisons.

    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. 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. 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. 3.Step 3: State both comparative figures clearly.
    Final Answer: (i) Linear search: 128 comparisons. (ii) Binary search: 8 comparisons.
    Active Recall Memory Test
    What essential prerequisite must a dataset meet before a binary search can be performed?
    Key Fact: The dataset must be sorted in order (ascending or descending).
    What is the maximum number of comparisons a linear search will make on an array containing n elements?
    Key Fact: n comparisons (worst-case occurs when the item is at the end or not present).
    What arithmetic operation is used to calculate the middle index in a binary search, and what is the formula?
    Key Fact: Integer division (DIV); formula: mid = (low + high) DIV 2.
    What is the best-case number of comparisons for both linear search and binary search?
    Key Fact: 1 comparison (when the target item is at index 0 for linear search, or at the exact initial midpoint for binary search).
    Frequently Asked Questions
    Why don't we always use binary search if it is faster?
    Binary search requires the dataset to be in sorted order. If you have an unsorted dataset and only need to perform a single search, sorting the list first takes far more computational effort and time than simply scanning through it with a linear search. Linear search is also simpler to implement and works on linked structures where direct index access is not possible.
    How does binary search calculate the middle item when an array has an even number of elements?
    Binary search uses integer division (DIV), which discards any remainder or fractional part. For example, if low is 0 and high is 5, the calculation is (0 + 5) DIV 2 = 2. This selects the item at index 2 (the lower middle item) rather than causing an error or using a decimal.
    Do I need to write Big O notation for searching algorithms in AQA GCSE Computer Science?
    No, Big O notation (such as O(n) or O(log n)) is strictly an A-Level requirement. For AQA GCSE, you only need to describe algorithmic efficiency in terms of the number of comparisons made, how the number of comparisons changes as dataset size increases, and best/worst-case scenarios.
    How does a binary search algorithm detect that an item is not in the list?
    A binary search checks the condition `WHILE low <= high`. Each time the item is not at the midpoint, the pointers move inward (`low = mid + 1` or `high = mid - 1`). If the target is absent, `low` eventually becomes strictly greater than `high`, causing the loop to terminate and returning a value indicating the target was not found.