Linear search checks items one by one until it finds the target or reaches the end. It is the simplest search algorithm.
Linear search is useful as a baseline because it shows what the algorithm does when it has no extra structure to exploit.
Core Idea
If the input is unsorted and no index or hash table is available, the algorithm may have to inspect each element. The worst case is that the target is absent or appears at the last position.
The time complexity is O(n). The extra space is usually O(1).
Linear search is not only for exact equality. The same pattern can find the first item satisfying any condition: first negative number, first user with a matching ID, first interval that overlaps, or first value above a threshold.
Function Contract
find_index(values, target) expects a sequence of values and a target value.
It returns the index of the first occurrence of target. If target does not appear, it returns -1. The function makes no sorted-order assumption.
Python Example
def find_index(values, target):
for index, value in enumerate(values):
if value == target:
return index
return -1The loop stops as soon as the target is found.
Step-by-Step Trace
For:
find_index([8, 4, 9, 2], 9)the algorithm checks index 0, then index 1, then index 2. It returns 2 when it sees 9.
For:
find_index([8, 4, 9, 2], 7)the algorithm checks all four values and returns -1.
Why It Is the Baseline
Linear search makes no assumption about the input order. Because it knows nothing useful about where the target might be, each unchecked element remains a possible answer.
Better search algorithms become possible only when the input has extra structure, such as sorted order or a hash map built in advance.
Common Confusions
Linear search is not bad by default. For small inputs, one pass is often enough and easier to trust than a more complex structure.
It is also not the same as checking membership with target in values, although Python may perform a linear search internally for lists.
Returning the first match is a design choice. If the problem asks for all matches, the algorithm must keep scanning after finding one.
When To Use It
Use linear search when the input is small, unsorted, or searched only once. If many searches are needed, sorting or a hash-based structure may be worth the extra setup.
It is also a good first solution when studying a problem. Once the direct scan is clear, it becomes easier to see what repeated work a better algorithm must remove.
The Main Point
Linear search is the baseline when no structure is available. It checks candidates directly and stops only when the answer is found or the input is exhausted.