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
- 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
- 1Day 1-2: Understand algorithm logic, write standard linear search pseudocode, and trace algorithms on small unsorted arrays.
- 2Day 3-4: Derive the best, worst, and average-case Big-O complexities and calculate exact comparison counts for varying array sizes.
- 3Day 5-6: Compare linear search with binary search across different data structures (arrays vs linked lists) and data states (ordered vs unordered).
- 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)
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).
Identify both similarities and differences between two algorithms (e.g., linear vs binary search), explicitly addressing time complexity, space complexity, and preconditions.
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)
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.Step 1: Identify list length (n). Here, n = 7.
- 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.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.Step 4: Determine Big-O complexity. The number of operations grows proportionally to n. Therefore, worst-case time complexity is 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.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.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.Step 3: Conclude suitability. Linear search handles both unordered sequences and sequential pointer traversal naturally.
- 4.Step 4: Determine space complexity. Linear search inspects records in place without allocating additional auxiliary memory structures, requiring only pointer/index variables.