Browser lab15 min+60 XP

Linear search

Check every item one by one. Simple, reliable, and sometimes too slow.

0% done

Code runs right here in your browser. Nothing to install.

TASK 1

Learn it

Key idea

Linear search checks every item in order until it finds a match.

Key words
linear_search(names, "Fin")"Zed"index 0check 1"Amy"index 1check 2"Rio"index 2check 3"Fin"index 3check 4"Ivy"index 4not needednononofound!returns 3 after 4 checks
Searching for "Fin": four checks, one item at a time.

A search algorithm finds the position of a value in a list. The simplest is linear search: start at the beginning and check each item in turn until you find it or reach the end.

It works on any list, sorted or not. But if the item is last, or missing, you check every item. For a list of a million names, that could be a million checks.

Python's in and .index() use linear search behind the scenes. Writing it yourself shows what they really do.

Real life linkLooking for your keys by checking every pocket in turn is a linear search. It always works, and it is slow when there are a lot of pockets.
Example code
def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

names = ["Zed", "Amy", "Rio", "Fin", "Ivy"]
print(linear_search(names, "Fin"))
print(linear_search(names, "Bob"))
TASK 2

Try it yourself

+10 XP

Change linear_search so it also counts how many comparisons it made, and returns a tuple (position, comparisons). Searching for Ivy should print (4, 5).

Create a free account to start this lab

Sign in to write, run and check your code here. Your progress, XP and code are saved to your account. No card needed.

TASK 3

Capture the flag

+10 XP

Does linear search need the list to be sorted? (yes or no)

Create a free account to start this lab

Sign in to answer the flag question. Your progress, XP and code are saved to your account. No card needed.

HOMEWORK

Find them all

+20 XP

Write find_all(items, target) that uses a linear search to return a list of every position where the target appears. find_all([3, 7, 3, 9, 3], 3) returns [0, 2, 4]. Also print the result for a value that is missing (an empty list).

Create a free account to start this lab

Sign in to do this homework and have it checked. Your progress, XP and code are saved to your account. No card needed.