Skip to topic
    ← Back to course topics

    Linear search — AQA A-Level Computer Science

    A linear search is a sequential algorithm that inspects every item in an array or list one by one until the target value is found or the end of the data set is reached. It operates with a worst-case time complexity of O(n) and has the primary advantage of functioning on completely unordered data.

    Linear search explained

    A linear search checks each element of a list in turn, starting at the first element and moving forward until it either finds the target value or reaches the end of the list.

    Read the full explanation

    The statement asks learners to know this algorithm and to be able to trace and analyse it. Tracing means working through the algorithm step by step on a given list and target, recording the index being examined, the comparison made and the outcome at each step; this shows exactly when and why the search stops. Analysing means reasoning about its behaviour: in the best case the target is the first element and one comparison is needed; in the worst case the target is absent or is the last element, so every one of the n elements must be compared. Because the list is not required to be ordered, linear search works on any list, but it is slower on large lists than methods that exploit order.

    Your focus

    1. Know and be able to trace and analyse the

    Which command word is this?

    Set out the reasons or mechanisms behind an algorithm behavior, linking technical causes to consequences (e.g., explaining why linear search is O(n) by linking iterations to input size).

    Linear search exam tips

    Topic Overview

    A linear search is one of the fundamental searching algorithms in AQA A-Level Computer Science, introducing students to sequential traversal and algorithmic evaluation. It functions by starting at the first element of a data structure and comparing each successive element to the target key until a match occurs or all elements have been examined.

    Within the broader curriculum, linear search establishes the benchmark for algorithm efficiency and Big-O notation. Understanding its performance characteristics allows students to evaluate trade-offs between algorithm complexity, data preconditions, and underlying data structures such as static arrays versus dynamically linked lists.

    Key Concepts
    • →Sequential Traversal: Elements are checked strictly in sequence from the beginning (index 0) to the end (index n - 1).
    • →Time Complexity: Best-case time complexity is O(1) (target found at index 0); worst-case and average-case time complexities are O(n).
    • →Space Complexity: Operates in-place with auxiliary space complexity of O(1), requiring negligible additional memory.
    • →Data Preconditions: Requires no preconditions; it operates effectively on unsorted data and dynamic sequential structures like linked lists.
    Marking Points
    • States that linear search examines elements one at a time from the start of the list until the target is found or the list ends.
    • Traces an example by recording each index examined, the comparison and whether the search continues or stops.
    • Identifies the best case as one comparison, when the target is the first element.
    • Identifies the worst case as n comparisons, when the target is absent or is the last element.
    • Explains that linear search does not require the list to be sorted.
    Examiner Tips
    • 💡When tracing, write a table with columns for index, value compared and result so each step is visible.
    • 💡Check whether the question asks about the best, worst or average case before giving a count of comparisons.
    • 💡Confirm the algorithm's termination conditions: a match, or reaching the end of the list.
    • 💡Always state Big-O notation using capital 'O' followed by parentheses containing the variable, such as O(n) or O(1).
    • 💡When asked why linear search is chosen for a specific scenario, reference both the state of the data (unsorted) and the size of the dataset.
    • 💡In trace tables, record every comparison made up to and including the matching value, and stop tracing immediately once the target is located.
    Common Mistakes
    • Stops tracing at the first match in the wrong place or continues past a match; correct by stopping at the first position where the target is found.
    • States that the worst case is one comparison; correct by identifying the worst case as examining every element.
    • Claims that linear search needs a sorted list; correct by explaining that it works on unordered data.
    • Thinking binary search is always superior: If a data set is small or unsorted and searched only once, sorting first to run binary search takes O(n log n), which is far slower than a direct O(n) linear search.
    • Assuming linear search must always check every item: An efficient linear search terminates immediately when the target is found, only checking all items if the target is in the last position or absent.
    • Believing linear search cannot work on linked lists: Linear search is actually the standard searching method for linked lists because they natively require sequential pointer navigation.
    Revision Plan
    1. 1Day 1-2: Understand algorithm logic, write standard linear search pseudocode, and trace algorithms on small unsorted arrays.
    2. 2Day 3-4: Derive the best, worst, and average-case Big-O complexities and calculate exact comparison counts for varying array sizes.
    3. 3Day 5-6: Compare linear search with binary search across different data structures (arrays vs linked lists) and data states (ordered vs unordered).
    4. 4Day 7: Complete past exam questions focusing on code implementation, trace tables, and algorithmic evaluation.
    Exam Question Types
    • 📋Algorithm Writing: Writing pseudocode or structured English to implement a linear search with early exit.
    • 📋Trace Tables: Tracing comparison counts and index pointers as the algorithm executes across a provided array.
    • 📋Comparative Evaluation: Extended response evaluating whether linear or binary search should be selected based on dataset state, size, and search frequency.
    Command Word Expectations (AQA)
    Explain

    Set out the reasons or mechanisms behind an algorithm behavior, linking technical causes to consequences (e.g., explaining why linear search is O(n) by linking iterations to input size).

    Compare

    Identify both similarities and differences between two algorithms (e.g., linear vs binary search), explicitly addressing time complexity, space complexity, and preconditions.

    Write / Develop

    Produce syntactically valid pseudocode or high-level program code that accurately fulfills all specified logic requirements, including boundary conditions and loop terminations.

    How Students Lose Marks (Examiner Pitfalls)
    Pitfall: Stating that linear search requires sorted data, conflating its requirements with binary search.
    ❌ Weak Answer (Loses Marks):A linear search checks elements in order, so the array must be sorted in ascending order first.
    Example improved answer:A linear search does not require the data set to be sorted; it iterates sequentially through elements in any order, making it suitable for unordered arrays and linked lists.
    Examiner Tip: In comparative exam questions, always explicitly state that linear search operates on unordered data, whereas binary search requires a pre-sorted data structure.
    Pitfall: Failing to implement an early exit in pseudocode, resulting in the algorithm redundantly continuing after finding the target.
    ❌ Weak Answer (Loses Marks):FOR i = 0 TO LEN(arr) - 1 IF arr[i] == target THEN found = True ENDIF ENDFOR
    Example improved answer:found = False i = 0 WHILE i < LEN(arr) AND NOT found IF arr[i] == target THEN found = True ELSE i = i + 1 ENDIF ENDWHILE RETURN found
    Examiner Tip: Use a WHILE loop or an explicit RETURN statement inside your selection construct to terminate execution immediately upon finding the target item.
    Step-by-Step Worked Solutions

    Question: An array contains the following items: [14, 8, 22, 5, 19, 31, 12]. Calculate the maximum and average number of comparisons required to search for an item using linear search, and explain the worst-case Big-O time complexity.

    1. 1.Step 1: Identify list length (n). Here, n = 7.
    2. 2.Step 2: Determine maximum comparisons. In the worst-case scenario (the target is the final item, 12, or is absent from the array), the algorithm checks every element once. Maximum comparisons = 7.
    3. 3.Step 3: Calculate average comparisons. Assuming uniform distribution where each item is equally likely to be searched, average comparisons = (n + 1) / 2 = (7 + 1) / 2 = 4 comparisons.
    4. 4.Step 4: Determine Big-O complexity. The number of operations grows proportionally to n. Therefore, worst-case time complexity is O(n).
    Final Answer: Maximum comparisons: 7; Average comparisons: 4; Worst-case time complexity: O(n).

    Question: A developer needs to search for an ID in an unordered linked list containing 20,000 records. Explain why a linear search is appropriate, and state its space complexity.

    1. 1.Step 1: Assess data organization. The data is unordered, which immediately rules out standard binary search unless an expensive sorting operation (O(n log n)) is run beforehand.
    2. 2.Step 2: Assess data structure characteristics. Linked lists do not support random access via index in O(1) time; pointers must be traversed sequentially node-by-node, making binary search inefficient even if sorted.
    3. 3.Step 3: Conclude suitability. Linear search handles both unordered sequences and sequential pointer traversal naturally.
    4. 4.Step 4: Determine space complexity. Linear search inspects records in place without allocating additional auxiliary memory structures, requiring only pointer/index variables.
    Final Answer: Linear search is appropriate because the list is unordered and linked lists only allow sequential access. Its auxiliary space complexity is O(1) (constant space).
    Active Recall Memory Test
    What is the worst-case and best-case time complexity of linear search?
    Key Fact: Worst-case is O(n); Best-case is O(1).
    What data condition must be satisfied before a linear search can be executed?
    Key Fact: None; linear search can execute on unordered or ordered data.
    What is the auxiliary space complexity of an iterative linear search?
    Key Fact: O(1) (constant space).
    Under what circumstance would a linear search perform fewer comparisons than a binary search on the same sorted array?
    Key Fact: When the target item is located at the very first index of the array (requiring only 1 comparison in linear search).
    Frequently Asked Questions
    Why would anyone use linear search instead of binary search?
    Linear search is used when the data collection is unsorted, because sorting a list takes at least O(n log n) time, which is inefficient if you only need to perform a single search. It is also suitable for small lists where the performance difference is negligible, and for data structures like linked lists that lack random access capabilities.
    Can linear search be implemented recursively?
    Yes, linear search can be written recursively by passing the current index to the function, checking the current element, and recurring with index + 1 if not found. However, in imperative languages, this is rarely practical because it consumes O(n) auxiliary call stack space compared to O(1) for an iterative loop.
    How do you calculate the average number of comparisons in linear search?
    Assuming the target is guaranteed to be present and all positions are equally likely, the average number of comparisons is the sum of positions from 1 to n divided by n, which simplifies to (n + 1) / 2. If the item may not be present, the calculation incorporates the probability of an unsuccessful search requiring n comparisons.
    What happens in a linear search if the array contains duplicate targets?
    A standard linear search traversing from left to right will locate and return the index of the first occurrence of the duplicate value before terminating. If designed to find all occurrences, it must traverse the entire array without early exit, maintaining an O(n) run time regardless of position.