Array traversal application: linear search

Array traversal application: linear search

Where linear search fits at N5

In programming, the same types of problems come up again and again: searching for a value in a list, finding the largest number, and counting how many items meet a condition. Programmers use well-tested, reusable patterns instead of inventing the same logic from scratch each time.

The N5 specification names exactly three standard algorithms:

• Input validation
• A running total within a loop
• Traversing a one-dimensional array

Linear search is not a separately named N5 standard algorithm. It is a useful application pattern built from the prescribed array traversal: visit each element in order and compare it with a target. This lesson gives extra practice with traversal, selection, Boolean flags, and positions.

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 index in range(len(array)):
    if array[index] == target:
        found = True
        position = index

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

When this code runs, index takes values 0, 1, 2, 3, 4 in turn. At index = 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.