Linear Search
DSA · Arrays and Searching
Theory
Linear search checks each element one by one from the start until it finds the target or reaches the end. It works on any list, sorted or not, and needs no extra memory. Its worst-case time is O(n) because the target may be last or missing; the best case is O(1) when the target is first.
Why we use it
It is the simplest search, requires no preparation, and is often the fastest choice for small or unsorted data.
When to use it
Use linear search for small lists, unsorted data, one-off searches, or when you need every match rather than one.
How it works
- Start: i = 0
- Is i < n? Yes: Compare arr[i] with target. No: Return -1 (not found).
- arr[i] == target? Yes: Return i (found). No: i = i + 1, repeat.
Syntax
for i from 0 to n-1:
if arr[i] == target: return i
return -1
Time: O(n) Space: O(1)Example
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
cities = ["Pune", "Delhi", "Mumbai", "Jaipur"]
print("Mumbai found at index", linear_search(cities, "Mumbai"))
print("Chennai found at index", linear_search(cities, "Chennai"))Key points
- Works on unsorted data
- O(n) time, O(1) space
- Returns -1 (or None) when not found
- Simple and good enough for small inputs