DSA Linear Search
Linear search checks each element of a list in order, one at a time, until it finds the target value or reaches the end of the list.
How Linear Search Works
Linear search is the simplest search algorithm: starting from the first element, it compares each item to the target value. If it finds a match, it returns immediately. If it reaches the end of the list without a match, it reports that the target is not present. It requires no assumptions about the order of the data.
- Start at the first element of the list.
- Compare the current element to the target value.
- If they match, return the current index immediately.
- Otherwise, move to the next element and repeat.
- If the end of the list is reached with no match, report that the target was not found.
Example
def linear_search(arr, target):
for index, value in enumerate(arr):
if value == target:
return index
return -1
numbers = [15, 8, 42, 4, 23, 16]
print(linear_search(numbers, 23))
print(linear_search(numbers, 99))Searching for Multiple Matches
Because linear search examines every element in sequence, it naturally extends to finding every occurrence of a value rather than stopping at the first one. This is something binary search cannot do directly, since binary search only locates a single position and requires sorted data to work at all.
Example
def find_all_indices(arr, target):
indices = []
for index, value in enumerate(arr):
if value == target:
indices.append(index)
return indices
data = [3, 7, 3, 9, 3, 1]
print(find_all_indices(data, 3))Complexity Analysis
Example
def find_first_matching(arr, predicate):
for index, value in enumerate(arr):
if predicate(value):
return index, value
return -1, None
ages = [12, 19, 25, 17, 30]
index, value = find_first_matching(ages, lambda age: age >= 18)
print(index, value)Exercise: DSA Linear Search
How does linear search look for a target value in a list?
