Linear search
Check every item one by one. Simple, reliable, and sometimes too slow.
Code runs right here in your browser. Nothing to install.
Learn it
Linear search checks every item in order until it finds a match.
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.
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"))
Try it yourself
+10 XPChange 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.
Capture the flag
+10 XPDoes 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.
Find them all
+20 XPWrite 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.