Imagine looking for a specific book on a disorganised shelf. You start from one end and check each book in turn until you find the one you want — or reach the end without finding it. This is exactly how linear search works: it checks items one by one from start to finish.
How Linear Search Works
- Start at the first item in the list.
- Compare it with the target value.
- If they match — found it! Return the position.
- If not — move to the next item.
- If you reach the end without a match — the item is not in the list.
Python Implementation
def linear_search(items, target):
for i in range(len(items)):
if items[i] == target:
return i # return the index where target was found
return -1 # -1 indicates "not found"
fruits = ["banana", "apple", "cherry", "mango"]
result = linear_search(fruits, "cherry")
print(result) # 2
result = linear_search(fruits, "grape")
print(result) # -1
Returning -1 for "not found" is a common convention. Always check the result before using it as an index! Some implementations return None instead, which can also be useful.
A Shorter Python Version
Python's in operator and index() method perform linear searches automatically:
fruits = ["banana", "apple", "cherry", "mango"]
if "cherry" in fruits:
print("Found at index:", fruits.index("cherry"))
Under the hood, this is doing the same thing — checking each item until a match is found.
Best and Worst Cases
| Scenario | Comparisons needed |
|---|---|
| Target is the first item | 1 |
| Target is the last item | n |
| Target is not in the list | n |
| Average case | n / 2 |
For a list of n items, linear search checks at most n items. We describe this as O(n) time complexity — doubling the list size roughly doubles the time.
Linear search is perfectly fine for small lists (under a few hundred items). It only becomes a problem for very large datasets where speed matters.
Advantages and Disadvantages
| Advantage | Disadvantage |
|---|---|
| Works on unsorted lists | Slow for large lists |
| Simple to implement | Checks every item until target found |
| Works on any data type | O(n) time complexity |
If you have a sorted list and you need to search it frequently, consider binary search instead. Binary search is far more efficient for large sorted lists, but linear search is your only option if the list is unsorted.
A Practical Example
def find_student(students, name):
for index, student in enumerate(students):
if student.lower() == name.lower():
return index
return -1
register = ["Alice", "Bob", "Carlos", "Diana", "Eve"]
pos = find_student(register, "carlos")
if pos != -1:
print(f"Found at position {pos}")
else:
print("Student not found")
Practice Problems
In the worst case, how many comparisons does linear search make on a list of 20 items? When does the worst case occur?
Show answer
What does linear search return if the target is not found in the list (using the implementation shown above)?