A-Level Computer Science / Unit 10: Organising Data in Programs

10.2.3 Finding Values with Linear Search

🔒 Lesson slides are available to signed-in users. Sign in

10.2.3 Finding Values with Linear Search

A linear search examines the elements of a one-dimensional array in index order. It compares each element with a required value and stops when a match is found or when every valid index has been checked.

By the end of this section, you should be able to:

  • Explain how a linear search checks an array.
  • Trace successful and unsuccessful searches.
  • Use a current index, search target and Boolean flag accurately.
  • Write pseudocode that stops when a match is found or the upper bound is passed.
  • Explain why linear search can be used with unsorted data.
  • Recognise that a search which stops at the first match returns the first matching index.

How Linear Search Works

A community repair workshop stores seven job reference codes in the order in which the jobs were registered. The array is not alphabetically sorted.

Index 4 5 6 7 8 9 10
RepairCode "RP-814" "LT-309" "CM-552" "TB-207" "RP-446" "PH-930" "KB-118"

Suppose the target is "TB-207". The search begins at the lower bound, index 4. It compares one element at a time:

  1. Compare RepairCode[4] with "TB-207".
  2. If they are different, advance to index 5.
  3. Continue until a match is found or index 10 has been checked.
Linear search: a search method that checks array elements one after another until the target is found or no unchecked elements remain.
Exam tip: State both stopping conditions: stop on a match, or stop after the final valid index has been processed.

Worked Trace: A Successful Search

The target "TB-207" is stored at index 7. The algorithm does not know this in advance, so it starts from the lower bound.

Comparison CurrentIndex Array value Matches target? Next action
1 4 "RP-814" FALSE Move to index 5
2 5 "LT-309" FALSE Move to index 6
3 6 "CM-552" FALSE Move to index 7
4 7 "TB-207" TRUE Set Found to TRUE and stop
The search uses four comparisons and returns index 7. Elements at indexes 8, 9 and 10 are not examined because the required value has already been found.
Common mistake: Do not call index 7 the “seventh element”. Because the lower bound is 4, index 7 is the fourth element in this array.

Data Used by the Algorithm

Clear identifiers make the search logic easier to follow and adapt.

Identifier Data type Purpose
RepairCode ARRAY[4:10] OF STRING Stores the job reference codes.
WantedCode STRING Stores the value being searched for.
CurrentIndex INTEGER Identifies the element currently being compared.
LowerBound INTEGER Stores the first valid array index.
UpperBound INTEGER Stores the final valid array index.
Found BOOLEAN Records whether a matching value has been encountered.
A Boolean flag is useful because it can control the loop and also be tested after the loop to decide which output is required.

Linear Search Pseudocode

This version uses a pre-condition loop. The current index starts at the lower bound and is increased only after an unsuccessful comparison. 

DECLARE RepairCode : ARRAY[4:10] OF STRING
DECLARE WantedCode : STRING
DECLARE CurrentIndex : INTEGER
DECLARE LowerBound : INTEGER
DECLARE UpperBound : INTEGER
DECLARE Found : BOOLEAN

LowerBound ← 4
UpperBound ← 10

INPUT WantedCode

CurrentIndex ← LowerBound
Found ← FALSE

WHILE CurrentIndex <= UpperBound AND Found = FALSE DO
    IF RepairCode[CurrentIndex] = WantedCode
      THEN
        Found ← TRUE
      ELSE
        CurrentIndex ← CurrentIndex + 1
    ENDIF
ENDWHILE

IF Found = TRUE
  THEN
    OUTPUT "Code found at index ", CurrentIndex
  ELSE
    OUTPUT "Code not found"
ENDIF

What each part achieves

Pseudocode part Purpose
CurrentIndex ← LowerBound Begins at the first valid element.
Found ← FALSE Records that no match has been seen yet.
CurrentIndex <= UpperBound Prevents the loop from processing an invalid index.
Found = FALSE Keeps searching only while no match has been found.
CurrentIndex ← CurrentIndex + 1 Moves to the next element after a failed comparison.

Stopping Safely at the Array Bounds

A correct linear search must never read an element beyond the array's upper bound. In the example, RepairCode[11] does not exist.

The loop condition checks that CurrentIndex is still valid before the next array comparison takes place.

Unsuccessful example

If WantedCode is "MN-610", all seven valid elements are compared. After index 10 fails to match, CurrentIndex becomes 11. The condition CurrentIndex <= UpperBound is then FALSE, so the loop ends without accessing RepairCode[11].

Common mistake: Incrementing the index and immediately reading the next element without testing the bound can produce an out-of-range access.
When checking pseudocode, test the two boundary cases: the target is at the final valid index, and the target is absent.

Successful and Unsuccessful Searches

Outcome Final state Appropriate output
Target found Found = TRUE and CurrentIndex is the matching index Report the index or use the matching element.
Target absent Found = FALSE after all valid indexes have been checked Report that the value was not found.

Number of comparisons

  • Best case: the target is at the lower bound, so only one comparison is needed.
  • Later match: every preceding element is checked before the match.
  • Worst case: the target is at the upper bound or absent, so every element is checked.
For an array containing n elements, a linear search may need as many as n comparisons.

Unsorted Data and Duplicate Values

The array does not need to be sorted

Linear search does not depend on values being in numeric or alphabetical order. It can search data stored in registration order, arrival order or any other order because it checks every relevant element in sequence.

Common misconception: A linear search does not require a sorted array. Sorting may be useful for other reasons, but it is not a condition for this algorithm.

What happens when values are repeated?

If the array contains the target more than once, the algorithm above stops at the first matching index because Found becomes TRUE immediately.

Index 1 2 3 4 5
ZoneCode "N2" "W4" "N2" "S1" "E3"

Searching for "N2" returns index 1. To find every occurrence, the algorithm would need to continue to the upper bound and process each matching element instead of stopping after the first.

Interactive: Linear Search Animator

Choose a scenario and step through the comparisons. Watch the current index, comparison count and Boolean result change as the search moves across the array.

Search target "TB-207"
Current index 4
Comparisons 0
Found FALSE
Search status

Ready to compare the first valid element.

IF RepairCode[4] = "TB-207"

Common Mistakes and Misconceptions

  • Starting from 0 or 1 without reading the array's actual lower bound.
  • Using the number of elements as though it were automatically the upper bound.
  • Forgetting to initialise Found to FALSE.
  • Failing to advance the current index after an unsuccessful comparison.
  • Continuing after a match when the task asks only for the first occurrence.
  • Stopping after one failed comparison instead of checking the remaining elements.
  • Accessing an element after the current index has moved beyond the upper bound.
  • Assuming the array must be sorted before a linear search can be used.
  • Outputting CurrentIndex as a valid match when Found is still FALSE.

Practice

Task 1: Trace a successful search

SensorID is declared as ARRAY[8:13] OF STRING and contains:

Index 8 9 10 11 12 13
SensorID "NV-42" "AQ-18" "RX-63" "LM-05" "KT-71" "BZ-26"
  1. Trace a search for "LM-05".
  2. List the indexes examined.
  3. State the number of comparisons.
  4. State the final values of Found and CurrentIndex.

Task 2: Trace an unsuccessful search

Use the same array to search for "QJ-90".

  1. How many comparisons are made?
  2. Why must index 14 not be accessed?
  3. What should the algorithm output?

Task 3: Write and adapt pseudocode

  1. Write linear-search pseudocode for DECLARE TicketNumber : ARRAY[20:35] OF INTEGER.
  2. Use a Boolean variable called TicketFound.
  3. Output the matching index when the ticket is present.
  4. Explain one change needed to report every matching index when duplicate values are allowed.

Review

Question Strong answer should include
What is a linear search? A sequential comparison of array elements with a target value.
Where does the search begin? At the array's lower bound.
When should it stop? When a match is found or every valid index has been checked.
Why use a Boolean flag? To record the outcome and help control loop termination.
Must the array be sorted? No. Linear search can process unordered values.
What is returned when duplicates exist? This version returns the first matching index because it stops immediately.
Final exam tip: Check your algorithm using three cases: a match at the lower bound, a match at the upper bound and a target that is absent. These expose most index and termination errors.