Python Program for Linear Search (with Examples)
-1 if the target is not in the list. It works on any list, sorted or not.Linear search (also called sequential search) is the simplest way to find a value in a Python list. You look at the first item, then the second, and so on until you either find the target or run out of items. It is the algorithm you already use when you scan a shopping list for "milk".
It is not the fastest option for huge data, but it needs no sorting and no special data structure, so it is the right tool for small lists and for data that is in no particular order. This page gives you a complete program, explains each line, and shows alternatives such as list.index() and in.
| Input | A list of items and a target value to find |
|---|---|
| Output | The index of the first match, or -1 when the target is missing |
| Approach | Visit each item in order and compare it with the target |
| Time complexity | O(n) in the worst case; O(1) extra space |
Approach: how linear search works step by step
- Start at index
0. - Compare the item at the current index with the target.
- If they are equal, stop and return the current index.
- Otherwise move to the next index.
- If you pass the last item without a match, return
-1.
Returning -1 is a convention: a valid index is never negative in this function, so the caller can tell "not found" from "found at position 0". The best case is a match on the first item (one comparison); the worst case is a match on the last item or no match at all (n comparisons).
How the linear search code works
The function uses a for loop with enumerate() to get the index and the value together (see enumerate and zip). The first time value == target is true, return ends the function immediately, so later items are never checked. The return -1 line sits after the loop, so it only runs when the loop finished without finding anything.
scores = [45, 88, 72, 91, 60]
for index, value in enumerate(scores):
print(index, value)Other ways to search a list in Python
Python already has linear search built in, and you should usually prefer it in real programs:
| Tool | What it gives you | If the item is missing |
|---|---|---|
target in items | True or False | False |
items.index(target) | Index of the first match (see list.index()) | Raises ValueError |
items.count(target) | How many times it appears | 0 |
Your own linear_search() | Index of the first match | Returns -1 (your choice) |
When linear search is the right choice
Use linear search when the list is short, when it is unsorted, or when you search only once (sorting first would cost more than scanning). If you search the same large, sorted list many times, binary search needs only about log2(n) comparisons instead of n. For a million items that is roughly 20 steps instead of up to a million.
Examples you can run
Press Run, then edit the code and run it again.
Find the index of a score
linear_search() returns the position of the first match. Index counting starts at 0.
def linear_search(items, target):
for index, value in enumerate(items):
if value == target:
return index
return -1
scores = [45, 88, 72, 91, 60]
print(linear_search(scores, 72))
print(linear_search(scores, 50))Expected output2
-1
Find every position of a value
A small variation collects all matching indexes instead of stopping at the first one, so it always scans the whole list.
def find_all(items, target):
positions = []
for index, value in enumerate(items):
if value == target:
positions.append(index)
return positions
grades = ["B", "A", "C", "A", "A", "B"]
print(find_all(grades, "A"))
print(find_all(grades, "D"))Expected output[1, 3, 4]
[]
Edge cases: empty list and duplicates
With an empty list the loop body never runs, so the function returns -1. With duplicates only the first match is reported.
def linear_search(items, target):
for index, value in enumerate(items):
if value == target:
return index
return -1
print(linear_search([], 5))
print(linear_search([4, 9, 4, 9], 9))
print(linear_search(["asha", "ravi", "meena"], "ravi"))Expected output-1
1
1
Interactive search with user input
The program reads a name from the user and reports its position in a class list. input() always returns a string, which is exactly what the list holds here.
def linear_search(items, target):
for index, value in enumerate(items):
if value == target:
return index
return -1
students = ["Asha", "Ravi", "Meena", "John"]
name = input("Search for: ")
position = linear_search(students, name)
if position == -1:
print(name, "is not in the list")
else:
print(name, "found at index", position)Expected outputSearch for: Meena
Meena found at index 2
Common mistakes
Returning -1 inside the loop
✗ Wrong
def linear_search(items, target):
for index, value in enumerate(items):
if value == target:
return index
else:
return -1
print(linear_search([5, 8, 3], 3))✓ Right
def linear_search(items, target):
for index, value in enumerate(items):
if value == target:
return index
return -1
print(linear_search([5, 8, 3], 3))Only return -1 after the loop has checked every item. Put return -1 outside the loop, aligned with the for line.
Treating -1 as a real index
✗ Wrong
items = [10, 20, 30]
position = -1
print(items[position])✓ Right
items = [10, 20, 30]
position = -1
if position != -1:
print(items[position])
else:
print("not found")Always test if position != -1 (or == -1) before using the result as an index.
Python Program for Linear Search (with Examples): questions people ask
What is the time complexity of linear search?
Linear search is O(n): in the worst case it compares the target with all n items. The best case is O(1) when the first item matches, and it uses O(1) extra memory.
Does linear search need a sorted list?
No. Linear search works on any list because it checks every item in turn. Only binary search requires the list to be sorted.
What is the difference between linear search and list.index() in Python?
list.index() is a built-in linear search written in C, so it is faster, but it raises ValueError when the item is missing, while a hand-written function can return -1 or None instead.
Keep learning
Step-by-step lessons:
Python ListsPython for LoopsPython Functions
Related:
Python Binary Search Program (Iterative and Recursive)Python List index() MethodPython Program to Find the Largest Number in a ListPython enumerate() Function
More in algorithms:
Python Binary Search Program (Iterative and Recursive)Python Bubble Sort Program (with Explanation)Python Selection Sort Program (with Explanation)Python Tower of Hanoi Program (Recursion Explained) See all →