Python Program for Linear Search
Beginner Searching and sorting Time O(n) Space O(1)
Finds a value in a list by checking each item in turn, from the first to the last, until one matches.
Linear search, also called sequential search, asks nothing of the list: it doesn't have to be sorted, and the items can
be anything that == can compare. In [42, 7, 19, 3, 88, 25, 61], finding 88 takes five checks: 42, 7, 19, 3, then
88 at index 4. To say that an item isn't there, it has to check every item.
Program
def linear_search(items, target):
"""The index of target in items, or -1."""
for index, item in enumerate(items):
if item == target:
return index
return -1
numbers = [42, 7, 19, 3, 88, 25, 61]
print("Index of 88:", linear_search(numbers, 88))
print("Index of 50:", linear_search(numbers, 50))
Open in the editor Download linear_search.py
Output
Index of 88: 4
Index of 50: -1
How it works
Step through the program line by line: each step below shows up as its line runs.
- The loop goes through the list from the first item to the last.
enumerate()gives each item together with its index, so the function can say where it found the target. - If the item is the target, the function returns its index straight away: the items after it are never checked.
- If the loop ends without a match, every item has been checked and none was the target, so the function returns -1 to say it isn't there.
- The program searches an unsorted list for 88, which is in it, and 50, which isn't.
Searching for 88:
| Step | index | item | Then |
|---|---|---|---|
| 1 | 0 | 42 | Not 88: next item |
| 2 | 1 | 7 | Not 88: next item |
| 3 | 2 | 19 | Not 88: next item |
| 4 | 3 | 3 | Not 88: next item |
| 5 | 4 | 88 | Found it: return 4 |
Searching for 50 checks all 7 items, finds no match, and returns -1.
Time and space complexity
| Time | O(n) |
|---|---|
| Extra space | O(1) |
In the worst case, when the target is the last item or isn't in the list at all, the loop checks all n items, so the time is O(n): the search for 50 checks all 7. The best case is a target at the front, found in one check. A target somewhere in the list is found after about n/2 checks on average, which still grows in step with n. The function keeps only the loop's two variables, so its extra space is O(1). For a sorted list that is searched many times, binary search is much faster: at most 20 checks for a million items, where linear search may need a million.
Other ways to write it
With list.index()
A list's index() method does the same linear search, but raises a ValueError when the item isn't there, so the
function catches it and returns -1 (errors and exceptions).
def linear_search(items, target):
try:
return items.index(target)
except ValueError:
return -1
numbers = [42, 7, 19, 3, 88, 25, 61]
print(linear_search(numbers, 88), linear_search(numbers, 50))With a while loop
Some courses write the loop with an index that counts up by hand (while loops).
def linear_search(items, target):
index = 0
while index < len(items):
if items[index] == target:
return index
index += 1
return -1
print(linear_search([42, 7, 19, 3, 88, 25, 61], 19))Try it yourself
- Search for the first item (42), the last (61) and a few numbers that aren't in the list.
- Count how many items the loop checks, and print the count next to the result.
- Add a second 88 to the list: the function returns the first one's index. Change it to return a list of every index where the target appears.
- Search a list of names, such as
["Asha", "Ben", "Chen", "Dev"], for"Chen": the same function works for text.