Linear Search
How linear search works and its time complexity
Linear Search
Given a list of numbers, we need to find the index of the number — that is, find such that . If no such index exists, report that the element is not found.
How linear search works and its time complexity
Given a list of numbers, we need to find the index of the number — that is, find such that . If no such index exists, report that the element is not found.
Linear search goes through the list element by element and checks each one until it finds the target. In the worst case — when the element is at the very end or not present at all — it checks all elements. This gives a time complexity of .
Both implementations return the index of the first occurrence of x, or -1 if not found.
in OperatorPython has a built-in way to check membership with in:
This is linear search under the hood — it is O(n) just like the manual implementations above. It is convenient, but you should not use it in a tight loop when performance matters.
To get the index, use the list method .index(x):
.index(x) raises a ValueError if x is not in the list. To stay safe, check first:
Note that this calls linear search twice. If you need both safety and a single pass, use the manual implementation.
Linear search is not limited to finding a specific value. You can search for the first element satisfying any condition:
If you need every index where x appears, not just the first one:
A direct application of linear search — scan through and track the position of the smallest value seen so far:
Linear search is the right tool when:
For large sorted lists, binary search runs in O(log n) and is much faster — we will cover it in this module. For repeated lookups on unsorted data, converting to a set or dict gives O(1) average time — covered in the Built-in Data Structures module.
def search(a, x):
for i in range(len(a)):
if a[i] == x:
return i
return -1
def search(a, x):
i = 0
while i < len(a) and a[i] != x:
i += 1
if i == len(a):
return -1
return i
a = [3, 1, 4, 1, 5, 9]
print(6 in a) # False
print(5 in a) # True
a = [3, 1, 4, 1, 5, 9]
print(a.index(4)) # 2
print(a.index(1)) # 1 — returns first occurrence only
if x in a:
print(a.index(x))
else:
print(-1)
# First even number
def first_even(a):
for i in range(len(a)):
if a[i] % 2 == 0:
return i
return -1
# First element greater than threshold
def first_greater(a, threshold):
for i in range(len(a)):
if a[i] > threshold:
return i
return -1
def search_all(a, x):
indices = []
for i in range(len(a)):
if a[i] == x:
indices.append(i)
return indices
a = [1, 3, 2, 3, 4, 3]
print(search_all(a, 3)) # [1, 3, 5]
def min_index(a):
idx = 0
for i in range(1, len(a)):
if a[i] < a[idx]:
idx = i
return idx
a = [5, 3, 8, 1, 9, 2]
print(min_index(a)) # 3 — a[3] = 1