Linear search checks sequence elements one at a time, usually from the beginning, and stops when it finds the target or reaches the end. It works for arrays and linked lists, though its straightforward scan can require visiting every element. section 3.6 section 6.8
Its behavior changes slightly with the data structure:
- In a sorted array, stop an unsuccessful search when the current element is larger than the target; later elements cannot match. section 3.6
- In a linked list, traverse node by node until finding the value or reaching the end; additional links in a doubly linked list usually do not improve this search. section 6.18
- The worst-case running time is O(n), although a successful search may return after one iteration and an average successful search may inspect about half the elements. section 4.14
- Binary search can be faster on arrays because indexed middle-element access lets it discard half the remaining elements, an advantage linked lists generally lack. section 6.13
A sorted-array scan
Searching for 8 in a sorted array that reaches 9 requires checking every earlier element and then stopping at 9: the larger value proves that 8 is absent. The implementation returns the matching index or None. section 3.6
def linear_search(self, target):
for i in range(self._size):
if self._array[i] == target:
return i
elif self._array[i] > target:
return None
return None
View a compact implementation that scans an array, returns the matching index, and stops early when sorted order rules out the target. section 3.6
