Linear Search

Think about how you find a name in an unsorted class register. You start at the top and read down the list one name at a time until you reach the one you want — or until you run out of names. You do not need the list to be in any special order; you simply check every entry in turn. That everyday habit is a linear search.

A linear search does three simple things, over and over:

• 1. Look at the current element.
• 2. Is it the target? If yes — stop, success.
• 3. If no — move to the next element. Repeat until you find it or run off the end.

Try the linear search yourself. Change the array and target values, then click Start. Use Step to move one line at a time, or Play to auto-run. Watch the code highlight on the right while the simulation updates on the left.

1found = False
2for i in range(len(data)):
3    if data[i] == target:
4        found = True
5        break
6if found:
7    print("Found")
8else:
9    print("Not found")

The plan in plain English: set a flag found to False; loop through every element; if an element matches the target, set found = True and stop early with break. After the loop, the flag tells you what happened.

marks = [42, 17, 88, 53, 9, 61]
target = 53

found = False
for value in marks:
    if value == target:
        found = True
        break  # stop early — no need to keep looking

if found:
    print("Value found")
else:
    print("Value not found")

The trick is to return the loop counter i the instant you match. If the loop finishes without returning, you fall through to a final return -1. Because no real index is -1, the calling code can test for it cleanly.

Here the loop keeps going while there are elements left and we have not found the target yet. The condition does double duty: it stops at the end of the list, and it stops early on success.

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

Cambridge pseudocode — WHILE loop

Index <- 0
Found <- FALSE
WHILE Index < Size AND Found = FALSE
    IF List[Index] = SearchValue THEN
        Found <- TRUE
    ELSE
        Index <- Index + 1
    ENDIF
ENDWHILE
IF Found = TRUE THEN
    OUTPUT "Found at position ", Index
ELSE
    OUTPUT "Value not found"
ENDIF

The cost of a linear search is measured in comparisons. There are three cases worth knowing:

A clinic stores the appointment ID numbers booked for one day in a global 1D array bookings. The IDs are added in the order patients call, so they are not sorted.

bookings = [5081, 5044, 5119, 5007, 5066, 5093, 5012, 5070]

Fifteen exam-style linear search tasks. Each shows only the question — click Hint for the thought process, or Help for the worked solution.