Linear Search

The simplest way to find something in a list.

A linear search looks through a list one item at a time, from the start, until it finds what it is looking for — or runs out of items. It is the most basic search algorithm.

The idea

Imagine checking a register name by name, from the top, until you find the right person. That is a linear search: simple, and it works on any list — sorted or not.

Searching with a found flag

found.py

names = ["Ava", "Ben", "Cara", "Dan"]
target = "Cara"
found = False

for name in names:
    if name == target:
        found = True

if found == True:
    print(target, "is in the list")
else:
    print(target, "is not in the list")

Output

Cara is in the list

How it works

found starts as False — we assume the item is not there.
The loop checks every name against the target.
If one matches, we set found to True.
After the loop, found tells us whether the item was anywhere in the list.

Finding the position

position.py

numbers = [4, 8, 15, 16, 23]
target = 15
position = -1

for i in range(len(numbers)):
    if numbers[i] == target:
        position = i

if position == -1:
    print("Not found")
else:
    print("Found at index", position)

Output

Found at index 2

How it works

range(len(numbers)) lets us look at each index in turn.
If the value at that index matches, we remember the index in position.
We start position at -1 to mean 'not found yet', since -1 is never a valid index.
15 sits at index 2, so that is what is reported.

As a reusable function

search.py

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

print(linear_search([4, 8, 15, 16], 15))
print(linear_search([4, 8, 15, 16], 99))

Output

2
-1

How it works

The function returns the index as soon as it finds the target — return stops the loop immediately.
If the loop finishes without a match, it returns -1.
This is the standard, tidy way to write a linear search.

How linear search worksIt checks each item in turn, from the start. It works on any list, but can be slow on very large ones.

What you have learned

A linear search checks each item one at a time, from the start.
A found flag (True/False) or a position variable records the result.
Returning early from a function stops as soon as the item is found.
-1 is a common way to signal 'not found'.
It works on any list, sorted or not.