DSA Linear Search
Linear search looks for a target by checking each value in order from the start. It works on any list, sorted or not.
Find a present value
The loop compares values one by one. It stops and reports the index on a match.
nums = [12, 7, 19, 4]
target = 19
comparisons = 0
for index, value in enumerate(nums):
comparisons += 1
if value == target:
print("index:", index)
break
print("comparisons:", comparisons)Miss the target
A missing target forces a full scan. Every value is compared once.
nums = [12, 7, 19, 4]
target = 9
comparisons = 0
found = -1
for index, value in enumerate(nums):
comparisons += 1
if value == target:
found = index
break
print("index:", found)
print("comparisons:", comparisons)Example
nums = [12, 7, 19, 4, 15]
def linear_search(target):
comparisons = 0
for index, value in enumerate(nums):
comparisons += 1
if value == target:
return index, comparisons
return -1, comparisons
for target in [19, 12, 9]:
index, comparisons = linear_search(target)
print("target:", target, "index:", index, "comparisons:", comparisons)Key points
- Linear search checks each value in order from the start.
- A comparison is one check of a value against the target.
- A hit stops the search at once.
- A miss costs one comparison per value in the list.
- The comparison count grows in step with the list size.
In this example, the search for 19 stops after three comparisons. The search for 12 stops after one comparison. The missing 9 costs all five comparisons. The counts match the position of each target.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
A list holds 8 values and the target is absent. How many comparisons does linear search make?