Standard algorithms: linear search

Standard algorithms: linear search

What is a standard algorithm?

In programming, the same types of problems come up again and again: searching for a value in a list, finding the largest number, counting how many items meet a condition. Rather than solving these problems from scratch every time, computer scientists have developed standard algorithms — well-tested, widely understood solutions that every programmer knows.

At N5 level, you are expected to know three standard algorithms:

• Linear search — find a specific value in an array (this lesson)
• Finding the minimum and maximum — identify the smallest or largest value
• Counting occurrences — count how many elements meet a condition

For each algorithm, you must be able to: explain how it works, trace through it on a given array, and write it in both Python and N5 pseudocode.

The idea behind linear search

Imagine you have a list of 100 unsorted student scores written on separate slips of paper. You want to know if a particular score — say, 87 — is in the list, and if so, which slip it is on. The only reliable way is to check each slip, one at a time, until you either find 87 or reach the end of the list without finding it. That is exactly what a linear search does.

"Linear" means in a straight line — the algorithm processes elements sequentially, from the first to the last, without skipping. It does not require the array to be sorted, which makes it very flexible. The downside is that in the worst case (target not present or at the very end) it must check every element.

The two variables: found and position

A linear search uses two key variables set up before the loop begins:

• found — a Boolean variable, initialised to False. It becomes True as soon as the target is located.
• position — an integer variable, initialised to -1. It is updated to the index where the target is found. Keeping it as -1 after the loop means the target was never found.

Using -1 as the "not found" sentinel is a common convention in programming: it is an impossible array index (valid indices are 0 or greater), so it clearly signals "no match was found".

How the algorithm works — step by step

The loop visits every element from index 0 to the last index. On each iteration it compares the current element with the target. If they match, found is set to True and position is updated. After the loop, the values of found and position are used to print the result.

Note that the basic N5 version uses a fixed FOR loop and does not stop early when the target is found — it continues checking all remaining elements. The values of found and position simply stay as they were once the target is located.

Python implementation

Here is the complete Python code for a linear search:

array = [85, 72, 91, 68, 88]
target = 91
found = False
position = -1

for i in range(len(array)):
    if array[i] == target:
        found = True
        position = i

if found:
    print("Found at position", position)
else:
    print("Not found")

When this code runs, i takes values 0, 1, 2, 3, 4 in turn. At i = 2, array[2] equals 91 which matches target, so found becomes True and position is set to 2. The loop continues for indices 3 and 4 but no further matches occur. After the loop, the output is: Found at position 2.

N5 pseudocode — exam format

In the SQA exam, pseudocode uses specific keywords. The linear search in N5 pseudocode looks like this:

SET array TO [85, 72, 91, 68, 88]
SET target TO 91
SET found TO false
SET position TO -1
FOR index FROM 0 TO LEN(array) - 1 DO
    IF array[index] = target THEN
        SET found TO true
        SET position TO index
    END IF
END FOR
IF found = true THEN
    SEND "Found at position " & position TO DISPLAY
ELSE
    SEND "Not found" TO DISPLAY
END IF

Key differences from Python: use SET ... TO instead of = for assignment; use IF ... THEN ... END IF; use FOR index FROM 0 TO LEN(array) - 1 DO ... END FOR; use SEND ... TO DISPLAY instead of print(); use = (not ==) for comparison. The & symbol joins strings together.

Reading a trace table

Exam questions often ask you to trace a linear search — that means working through the algorithm by hand and recording the values of key variables at each step. A trace table is a grid showing the index, the array value at that index, whether it matches the target, and the current values of found and position.

When completing a trace table, work through every iteration even if the target has already been found — the basic FOR loop does not stop early, so you must show all rows.