What is linear search in algorithms?
Linear search, also called sequential search, checks each element of a collection in order until it finds the target or exhausts the search space. It works on sorted and unsorted data but takes O(n) time in the worst case.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
For an array of length n, linear search compares the target with elements at indices 0, 1, 2, and so on:
-
Start at the first element.
-
Compare the current element with the target.
-
Return the index immediately when they match.
-
If no match appears before the end, report that the target was not found.
This approach is commonly used when data is unsorted, the collection is small, or sorting would cost more than performing one search.
Complexity
Let n be the number of elements being searched.
| Case | Time | Reason |
|---|---|---|
| Best | O(1) | The first element matches the target. |
| Average | O(n) | The target is expected to appear somewhere among the elements. |
| Worst | O(n) | The target is last or absent, so every element is checked. |
-
Auxiliary space: O(1) because only a small number of variables, such as the current index, are needed.
-
Total space: O(n) when the input collection is included.
-
There is no recursive call stack.
-
Linear search is not amortized; each search independently performs up to
ncomparisons.
Example Walkthrough
Suppose the array is [12, 7, 25, 7, 30] and the target is 7.
| Step | Index | Value | Result |
|---|---|---|---|
| 1 | 0 | 12 | Not equal; continue. |
| 2 | 1 | 7 | Match found at index 1. |
A search for 25 would check indices 0, 1, and 2 before returning index 2. A search for 40 would inspect all five elements and return “not found.”
Linear Search vs. Binary Search
| Approach | Time | Space | Requirement | Best Use |
|---|---|---|---|---|
| Linear search | O(n) average and worst | O(1) auxiliary | No ordering required | Small or unsorted collections |
| Binary search | O(1) best; O(log n) average and worst | O(1) auxiliary for iterative search; O(log n) including the recursion stack for recursive search | Sorted data or a monotonic condition | Large, repeatedly searched collections |
The iterative binary-search implementation uses only search bounds and a midpoint, while a recursive implementation adds up to O(log n) stack frames.
Sorting an unsorted collection so binary search can be used may take O(n log n) time and O(1) auxiliary space for a standard in-place algorithm. Therefore, for only one search over unsorted data, linear search may be more efficient overall.
Edge Cases and Variations
-
Empty input: Return “not found” without performing comparisons.
-
One element: The only possible match is checked in O(1) time.
-
Duplicates: Returning the first match gives the lowest index; scanning the entire collection can find every occurrence.
-
Negative numbers: They require no special handling.
-
Already sorted input: Linear search still works, although binary search is faster when many searches are expected.
-
Repeated searches: If the same collection is searched frequently, sorting it and using binary search may be worthwhile.
Common Pitfalls and Interview Tips
-
Start the index at
0and use the conditionindex < len(collection)to avoid an out-of-bounds access. -
Decide whether the function should return the first matching index, all matching indices, or the element itself.
-
Do not use
list.pop(0)orlist.insert(0, value)to simulate a search; these operations are O(n) and can hide the linear-search behavior. -
Do not claim linear search is O(log n); its worst-case time is O(n) because it may inspect every element.
-
A common follow-up asks how linear search can find the first occurrence, the last occurrence, or the number of occurrences while retaining O(n) time and O(1) auxiliary space.