Sorting & Searching

AS Level

Linear Search

Learn the simplest searching algorithm — linear search. Walk through an array one element at a time, use a Found flag to track progress, and trace the algorithm step by step using CIE pseudocode.

22.1 What is Linear Search?

  • Linear search checks each element in an array one by one, from the start to the end.
  • Works on BOTH sorted and unsorted arrays — the order of values does not matter.
  • Simple to implement but slow for large arrays.
  • Stops when the target is found OR all elements have been checked.
  • Time complexity: O(n) — worst case checks all n elements.

Key idea: “Linear” means “in a line” — the algorithm walks through the array in a straight line from index 1 to index n. Also called sequential search for this reason.

Common mistake: Linear search is not the same as binary search. Binary search jumps to the middle of a sorted array and halves the search space each time — linear search just walks step by step.

22.2 Linear Search Algorithm

The algorithm uses a Found flag (BOOLEAN) and a WHILE loop so it can exit early when the target is located.

  • Step 1: Start at the first element (index 1).
  • Step 2: Compare the current element with the search value.
  • Step 3: If a match is found, report the position and stop.
  • Step 4: If no match, move to the next element (I <- I + 1).
  • Step 5: Repeat until found or end of array.

Example: search for a value in an array of 5 numbers

DECLARE Numbers : ARRAY[1:5] OF INTEGER
DECLARE SearchVal : INTEGER
DECLARE I : INTEGER
DECLARE Found : BOOLEAN
Found <- FALSE
I <- 1
OUTPUT "Enter value to search: "
INPUT SearchVal
WHILE I <= 5 AND NOT Found DO
  IF Numbers[I] = SearchVal THEN
    Found <- TRUE
  ELSE
    I <- I + 1
  ENDIF
ENDWHILE
IF Found THEN
  OUTPUT "Found at position ", I
ELSE
  OUTPUT "Not found"
ENDIF

Exam tip: The loop guard WHILE I <= 5 AND NOT Found DO does two jobs at once: it stops when I exceeds the array length (target not present) AND it stops the moment Found becomes TRUE (target located). This is the early-exit pattern examiners look for.

22.3 Tracing a Linear Search

  • A trace table records the value of key variables at each iteration.
  • Typical columns: I, Numbers[I], Found.
  • Each row in the table = one iteration of the loop.
  • The trace ends when Found becomes TRUE or I exceeds the array length.

Example: trace a search for 30 in [10, 20, 30, 40, 50]

IterationINumbers[I]Match?Found
1110No (10 ≠ 30)FALSE
2220No (20 ≠ 30)FALSE
3330Yes (30 = 30)TRUE → stop

Output: "Found at position 3"

Common mistake: When the match is found, I does not increment — the loop exits immediately with I still at the matching index. If you add 1 to I before exiting, you will report the wrong position.

22.4 Linear Search with FOR Loop

  • An alternative implementation uses a FOR loop instead of WHILE.
  • Simpler to write but always checks all elements (no early exit unless using a flag).
  • Use the guard AND NOT Found to record only the first match.
  • A separate Position variable is needed because I keeps changing.

Example: linear search using a FOR loop

DECLARE Numbers : ARRAY[1:5] OF INTEGER
DECLARE SearchVal : INTEGER
DECLARE I : INTEGER
DECLARE Found : BOOLEAN
DECLARE Position : INTEGER
Found <- FALSE
Position <- 0
OUTPUT "Enter value to search: "
INPUT SearchVal
FOR I <- 1 TO 5
  IF Numbers[I] = SearchVal AND NOT Found THEN
    Found <- TRUE
    Position <- I
  ENDIF
NEXT I
IF Found THEN
  OUTPUT "Found at position ", Position
ELSE
  OUTPUT "Not found"
ENDIF

WHILE loop — can exit early

Found <- FALSE
I <- 1
WHILE I <= 5 AND NOT Found DO
  IF Numbers[I] = SearchVal THEN
    Found <- TRUE
  ELSE
    I <- I + 1
  ENDIF
ENDWHILE

FOR loop — always full scan

Found <- FALSE
Position <- 0
FOR I <- 1 TO 5
  IF Numbers[I] = SearchVal AND NOT Found THEN
    Found <- TRUE
    Position <- I
  ENDIF
NEXT I

Key idea: The AND NOT Found guard inside the FOR loop prevents Position from being overwritten on later matches — so only the first occurrence is recorded. The loop itself still runs all 5 iterations because CIE pseudocode has no BREAK statement.

22.5 Practical Examples

  • Example 1: Search for a student name in a class list.
  • Example 2: Find if a number exists in a lottery ticket array.
  • Example 3: Search for a product by ID in an inventory array.
  • Example 4: Count how many times a value appears (modified linear search).

Example 4: count how many times a value appears

DECLARE Numbers : ARRAY[1:5] OF INTEGER
DECLARE SearchVal : INTEGER
DECLARE I : INTEGER
DECLARE Count : INTEGER
Count <- 0
OUTPUT "Enter value to count: "
INPUT SearchVal
FOR I <- 1 TO 5
  IF Numbers[I] = SearchVal THEN
    Count <- Count + 1
  ENDIF
NEXT I
OUTPUT "Value appears ", Count, " time(s)"

Exam tip: When a question asks you to count occurrences, remove the Found flag entirely — you want every match, not just the first. Replace it with a Count integer that increments on each match, and use a plain FOR loop with no early-exit guard.

22.6 Key Points Summary

Linear search checks elements sequentially (one by one).

Works on sorted AND unsorted arrays.

Uses a Found flag (BOOLEAN) to track if found.

WHILE loop version can exit early when found.

FOR loop version checks all elements (unless using a flag).

Worst case: target at the end or not present (n comparisons).

Best case: target is the first element (1 comparison).

Position variable records WHERE the target was found.

Time complexity: O(n) in the worst case.

Linear search is an AS Level topic.

Exam tip: Whenever an exam question says “search an unsorted array” or “find whether a value is present”, reach for linear search with a Found flag. If it asks you to count occurrences, swap the flag for a Count integer and remove the early-exit guard.

Question Bank

Answer all questions, then press Submit Quiz to see your score.

0/12 answered

Question 1Multiple Choice

Which array can be searched using linear search?

Question 2True / False

The worst-case time complexity of linear search is O(n).

Question 3Multiple Choice

DECLARE Numbers : ARRAY[1:5] OF INTEGER
DECLARE SearchVal : INTEGER
DECLARE I : INTEGER
DECLARE Found : BOOLEAN
Numbers[1] <- 8
Numbers[2] <- 2
Numbers[3] <- 6
Numbers[4] <- 9
Numbers[5] <- 1
SearchVal <- 9
Found <- FALSE
I <- 1
WHILE I <= 5 AND NOT Found DO
  IF Numbers[I] = SearchVal THEN
    Found <- TRUE
  ELSE
    I <- I + 1
  ENDIF
ENDWHILE
IF Found THEN
  OUTPUT "Found at position ", I
ELSE
  OUTPUT "Not found"
ENDIF

Question 4True / False

The Found flag is a BOOLEAN variable that records whether the search value has been located.

Question 5Multiple Choice

Which loop structure allows a linear search to exit EARLY as soon as the target is found?

Question 6Multiple Choice

DECLARE Numbers : ARRAY[1:5] OF INTEGER
DECLARE SearchVal : INTEGER
DECLARE I : INTEGER
DECLARE Found : BOOLEAN
Numbers[1] <- 4
Numbers[2] <- 7
Numbers[3] <- 1
Numbers[4] <- 9
Numbers[5] <- 2
SearchVal <- 5
Found <- FALSE
I <- 1
WHILE I <= 5 AND NOT Found DO
  IF Numbers[I] = SearchVal THEN
    Found <- TRUE
  ELSE
    I <- I + 1
  ENDIF
ENDWHILE
IF Found THEN
  OUTPUT "Found at position ", I
ELSE
  OUTPUT "Not found"
ENDIF

Question 7True / False

A standard FOR loop version of linear search always iterates through every element, even if the target is found at the first position.

Question 8Multiple Choice

What is the BEST case for a linear search on an array of n elements?

Question 9Multiple Choice

DECLARE Numbers : ARRAY[1:5] OF INTEGER
DECLARE SearchVal : INTEGER
DECLARE I : INTEGER
DECLARE Count : INTEGER
Numbers[1] <- 6
Numbers[2] <- 2
Numbers[3] <- 6
Numbers[4] <- 4
Numbers[5] <- 6
SearchVal <- 6
Count <- 0
FOR I <- 1 TO 5
  IF Numbers[I] = SearchVal THEN
    Count <- Count + 1
  ENDIF
NEXT I
OUTPUT Count

Question 10True / False

In the FOR loop version of linear search, the Position variable is needed because the loop variable I changes on every iteration.

Question 11Multiple Choice

Which variable would you use to count how many times a value appears in an array?

Question 12Multiple Choice

A linear search of an array of 1000 elements finds the target at position 999. How many comparisons were made?

Answer all 12 questions to enable submission.