📚 Knowledge Library — Topic 7.9 — Algorithm Design & Problem Solving

Linear Search Explained Simply

Learn how a linear search checks data one item at a time and stops when the target is found or every item has been checked.

Start Learning Worked Example
1. Invitation

A linear search checks one item at a time.

A linear search is a standard searching algorithm that checks each item in sequence.

It begins with the first item and continues until the target is found or every item has been checked.

💡 Key idea: start at the beginning, compare each item and move forward one position at a time.
Figure 1.1
Search in Order
First item
→
Next item
→
Next item
→
Found or finished
2. Big Idea

The data does not need to be sorted.

A linear search can work through numbers, names or other values in any order.

Its strength is simplicity. Its drawback is that the target may be near the end, so many comparisons may be needed.

💡 Linear search is simple and reliable, but not always fast for large data sets.
Figure 2.1
Unsorted Data Is Fine
14   3   27   8
↓
Still searchable
3. FutureLogic Bridge

Think of checking lockers for a missing bag.

You begin with the first locker, check inside and move to the next locker if the bag is not there.

You stop when the bag is found or after checking the final locker.

💡 Bridge: one locker, one check, one move forward.
Figure 3.1
The Locker Search
Locker 1
→
Locker 2
→
Locker 3
→
Bag found?
4. The Four-Step Method

Compare, decide, move and repeat.

1Start at the first item.
2Compare it with the target.
3Stop if it matches.
4Otherwise move to the next item.
💡 Repeat until the target is found or there are no items left.
5. Searching an Array

The index shows the current position.

Suppose the algorithm searches for the value 6.

Index 01
Index 15
Index 26
Index 39
Index 43
Index 58
Index 62

What happened?

Index 0 did not match. Index 1 did not match. Index 2 matched, so the search stopped.

The target value 6 was found at index 2.
6. When the Target Is Missing

The algorithm must also handle “not found.”

If the target does not appear, the algorithm continues until it reaches the end of the data.

Only then can it report that the item was not found.

💡 Do not say “not found” after the first failed comparison. The remaining items still need checking.
Figure 6.1
Search to the End
Check all items
↓
No match
↓
Output "Not found"
7. Using a Found Flag

A Boolean flag remembers whether a match has been found.

The variable Found can begin as FALSE.

When a match occurs, Found changes to TRUE and the loop can stop.

Key patternBoolean flag
Found ← FALSE

IF Data[Index] = SearchValue
  THEN
    Found ← TRUE
ENDIF
Figure 7.1
Flag State
Not found
Found = FALSE
↓
Match found
Found = TRUE
8. A More Efficient Search

Stop as soon as the target is found.

A basic FOR loop may continue checking even after a match.

A WHILE loop can stop when either the target is found or the end of the array is reached.

Efficient conditionTwo stop reasons
WHILE Found = FALSE
  AND Index < LENGTH(Data) DO
🎯 Exam Tip: both conditions matter—the item has not been found and unchecked data remains.
Figure 8.1
Stop Conditions
Found?
or
End reached?
↓
Stop search
9. Computational Thinking

Linear search uses a repeatable pattern.

SkillHow it appears
DecompositionThe search is split into repeated comparisons.
Pattern recognitionThe same compare-and-move pattern repeats.
AbstractionOnly the target, current item and position matter.
Algorithmic thinkingThe search follows a precise order and stopping rule.
💡 Linear search is a simple example of a repeatable algorithmic pattern.
Figure 9.1
Repeated Pattern
Compare
↓
Match?
↓
Move or stop
↺
10. Worked Example

Write a linear search for an array.

AlgorithmSearch Data[]
Found ← FALSE
Index ← 0

WHILE Found = FALSE
  AND Index < LENGTH(Data) DO

  IF Data[Index] = SearchValue
    THEN
      Found ← TRUE
    ELSE
      Index ← Index + 1
  ENDIF

ENDWHILE

IF Found = TRUE
  THEN
    OUTPUT "Found at index ", Index
  ELSE
    OUTPUT "Not found"
ENDIF

How it works

Found starts as FALSE and Index starts at the first element. Each item is compared with SearchValue. A match changes Found to TRUE; otherwise Index moves forward.

Model answer: “The algorithm searches each array element in order until the value is found or the end of the array is reached.”
11. Trace the Search

A trace table can show every comparison.

Search the array [4, 9, 2, 7] for the value 7.

IndexData[Index]SearchValueFound
047FALSE
197FALSE
227FALSE
377TRUE
💡 The search stops at index 3 because the target has been found.
12. Exam Tip

Know the difference between searching and sorting.

A linear search finds whether a target exists in a data set.

A bubble sort rearranges data into an order.

🎯 Linear search = find. Bubble sort = arrange.
Figure 12.1
Two Different Jobs
Search
= locate target

Sort
= reorder data
13. Common Mistakes

Do not skip the stopping logic.

✗ Common mistakes

Starting at the wrong index, not increasing Index, continuing after a match or reporting “not found” too early.

✓ Reliable method

Initialise, compare, update the flag or index, and stop only when found or finished.

⚠️ Every loop must make progress. If Index never changes, the search may become an endless loop.
14. Summary

Linear search in one screen.

A linear search checks each item in order from the beginning.

It compares the current item with the target and stops when a match is found or when all data has been checked.

A Boolean flag can record whether the target was found, while an index records the current position.

💡 Final thought: compare one, move one, repeat until found or finished.
Figure 14.1
Final Model
Start at first
↓
Compare
↓
Move or stop
↓
Report result