Key vocabulary

Linear search

What is a standard algorithm?

A standard algorithm is a well-known, reusable method for solving a common programming problem — one that has already been designed, tested, and proven to work, rather than something built from scratch every time the same problem appears. Higher requires three standard algorithms working on 1D arrays: linear search (this lesson), and finding a minimum, maximum, or counting occurrences (SDD14). SDD15 then re-runs all of these against arrays of records instead of plain arrays.

How linear search works

Linear search is the simplest standard search algorithm: starting at index 0, it checks each element of an array in order, comparing it to the target value, and stops as soon as a match is found — or, if it reaches the end of the array without a match, concludes the target isn't present at all. The word "linear" describes this straight-line, one-at-a-time scanning; every element up to and including the match must be checked, and in the worst case (target not present, or the very last element), every single element in the array is checked.

Implementing linear search with a found flag

A typical Higher implementation uses a Boolean found flag, starting as False, alongside an index counter starting at 0. A while loop continues as long as the index is still within the array's bounds and the target hasn't been found yet; inside the loop, each element is compared to the target, setting found to True if it matches, or advancing the index if it doesn't. Once the loop ends — either because the target was found, or because the index ran off the end of the array — the found flag (or the final index value) determines what gets returned.

Returning a result: index or sentinel value

Since a search is usually looking for a target's position, not just whether it exists, linear search normally returns the matching index if found. But what should it return if the target isn't in the array at all? No genuine array index is ever negative, so a sentinel value such as -1 is commonly used to signal "not found" — any code calling the search can then check whether the result is -1 before trying to use it as a real index.

Why an incrementing index matters

A very common bug is forgetting to advance the index inside the loop's "no match" branch. If the index is only ever incremented when a match is found, and the target is never actually present, the index never changes and the while condition never becomes false — the loop runs forever, checking the same element over and over. Getting the loop's increment step right, in every branch that doesn't immediately return or set the found flag, is essential to a working search.

Worked examples

itemNames = ["Chocolate", "Crisps", "Juice", "Flapjack", "Sweets", "Muffin"]

def linearSearch(array, target):
    index = 0
    found = False
    while index < len(array) and not found:
        if array[index] == target:
            found = True
        else:
            index = index + 1
    if found:
        return index
    else:
        return -1

result = linearSearch(itemNames, "Flapjack")

result = linearSearch(itemNames, "Kale")

stockLevels = [30, 45, 20, 15, 60, 18]
result = linearSearch(stockLevels, 15)

Task Set A — Core questions

def linearSearch(array, target):
    index = 0
    found = False
    while index < len(array) and not found:
        if array[index] == target:
            found = True
        else:
            index = index + 1
    if found:
        return index
    else:
        return -1

Task Set B — Extension