I always start explaining search algorithms with linear search, because it is the most direct, no-assumptions way I can look for something: I check each element one by one, in order, until I either find what I am looking for or run out of elements to check. It requires no preconditions about the data — unlike binary search, it works equally well on sorted or unsorted collections — and its simplicity makes it the natural baseline against which every other search algorithm gets compared. While it is not the fastest option for large datasets, I still reach for it constantly in small collections or one-off searches where the overhead of sorting or building a more complex structure simply isn’t worth it.
History and Background
Linear search does not have a formal “invention” the way more sophisticated algorithms do, since it reflects the most basic and intuitive method of searching — checking items one at a time — that predates computer science entirely, going back to how humans have always searched through physical collections of items. As one of the earliest algorithms formally described in computing literature, it appears in foundational texts from the 1950s and 60s as the natural starting point before more advanced searching techniques like binary search were introduced. It remains foundational in algorithm education specifically because its simplicity provides a clear baseline for teaching Big O notation and time complexity analysis.
Problem Statement
I need a method to determine whether a specific value exists within a collection, and if so, to find its position, without requiring any particular ordering of the data beforehand. Linear search solves this in the most direct way possible: examining each element sequentially until a match is found or the entire collection has been checked, making it applicable to any data structure that supports sequential access, regardless of whether it is sorted.
Core Concepts
- Sequential access: linear search only requires the ability to move through elements one at a time, making it applicable to arrays, linked lists, and other sequential structures alike.
- No sortedness requirement: unlike binary search, linear search makes no assumptions about the order of the data, which is both its main strength and the root of its inefficiency compared to faster alternatives.
- Early termination: as soon as a match is found, the search stops immediately rather than needlessly checking the remaining elements.
- Exhaustive check: if the target is not present, linear search must examine every single element before concluding this, which defines its worst-case behavior.
How It Works
I carry out linear search through these steps:
- I start at the first element of the collection.
- I compare the current element with the target value.
- If they match, I return the current index (or a “found” indicator) immediately.
- If they don’t match, I move to the next element and repeat the comparison.
- If I reach the end of the collection without finding a match, I conclude the target is not present and return an appropriate “not found” indicator.
Working Principle
The mechanism behind linear search is about as direct as an algorithm can get — there is no cleverness in eliminating candidates or narrowing a search space, only a straightforward, exhaustive comparison against every element in sequence. This directness is exactly why it works on any dataset, sorted or not, and on any data structure that permits sequential traversal, even those without random access like singly linked lists. The trade-off I always weigh is that this generality comes at the cost of efficiency: without any structural assumption to exploit, the algorithm has no way to skip over unpromising sections of the data.
Mathematical Foundation
For a collection of size n, if the target is present, the number of comparisons needed depends on its position. If the target is equally likely to be at any position (a uniform distribution assumption), the expected number of comparisons is:
$$E[\text{comparisons}] = \frac{1}{n}\sum_{i=1}^{n} i = \frac{n+1}{2}$$
giving an average-case time complexity of:
$$T_{avg}(n) = O(n)$$
In the worst case — where the target is the last element checked, or absent entirely — the algorithm performs exactly n comparisons:
$$T_{worst}(n) = O(n)$$
In the best case, where the target is the very first element:
$$T_{best}(n) = O(1)$$
Diagrams
flowchart TD
A[Start: i = 0] --> B{i < length of array?}
B -->|No| C[Target not found, return -1]
B -->|Yes| D{A of i equals target?}
D -->|Yes| E[Return index i]
D -->|No| F[i = i + 1]
F --> Bgraph LR
A["[5,3,8,2,9,1] target=9"] -->|"check 5, no match"| B["check 3, no match"]
B -->|"check 8, no match"| C["check 2, no match"]
C -->|"check 9, match!"| D["return index 4"]Pseudocode
LINEAR-SEARCH(A, target)
n = length(A)
for i = 0 to n - 1
if A[i] == target
return i
return -1 // target not found
Step-by-Step Example
I will search for the target value 9 in the array [5, 3, 8, 2, 9, 1].
Step 1: i=0. A[0] = 5. 5 ≠ 9, move on.
Step 2: i=1. A[1] = 3. 3 ≠ 9, move on.
Step 3: i=2. A[2] = 8. 8 ≠ 9, move on.
Step 4: i=3. A[3] = 2. 2 ≠ 9, move on.
Step 5: i=4. A[4] = 9. Match found! Return index 4.
Result: Target 9 found at index 4, after 5 comparisons.
If I instead searched for a value not present, such as 100, the algorithm would check all 6 elements before returning -1.
Time Complexity
- Best case: O(1) — occurs when the target is found at the very first position checked.
- Average case: O(n) — on average, assuming a uniform likelihood of the target’s position, roughly half the array needs to be scanned.
- Worst case: O(n) — occurs when the target is at the last position, or is absent entirely, requiring a full scan of the collection.
Space Complexity
Linear search requires only O(1) additional space, since it just needs a single index variable to track its current position during the scan. It needs no auxiliary data structures of any kind, making it as memory-efficient as an algorithm can be.
Correctness Analysis
I prove linear search’s correctness using a simple loop invariant: at the start of each iteration, the target has not been found in any of the previously checked positions A[0..i-1]. This holds trivially at the start, since no positions have been checked yet. During each iteration, I check A[i]: if it matches the target, I immediately return the correct index, which is provably correct since I have exhaustively confirmed no earlier position matched. If it does not match, the invariant extends to A[0..i], and I proceed to the next index. If the loop completes without finding a match, the invariant guarantees that every position in the array has been checked and found not to match, which correctly justifies returning “not found.”
Advantages
- Requires no preconditions on the data — works on unsorted collections just as well as sorted ones.
- Extremely simple to implement and understand, with no edge cases around data structure or ordering.
- Works on any sequentially accessible structure, including linked lists, where algorithms like binary search cannot be applied efficiently.
- Requires only O(1) additional memory.
- Efficient for very small datasets, where the overhead of more complex algorithms isn’t justified.
Disadvantages
- O(n) time complexity makes it inefficient for large datasets compared to O(log n) alternatives like binary search.
- Does not take advantage of any existing order in the data, even when the data happens to be sorted.
- Requires a full scan in the worst case, which can be costly for repeated searches on the same large, static dataset.
- Becomes a poor choice compared to hash-based lookups (O(1) average case) whenever fast, repeated membership testing is needed.
Applications
- Searching through small or unsorted datasets, where the simplicity outweighs the inefficiency for large-scale data.
- Searching linked lists or streaming data, where random access (required for binary search) is unavailable or impossible.
- One-off searches on data that isn’t going to be searched repeatedly, where the cost of sorting first would outweigh the benefit of a faster search algorithm.
- Used as a subroutine or fallback in more complex algorithms and libraries when dealing with very small subarrays, similar to how insertion sort is used as a fallback in hybrid sorting algorithms.
- Searching through unindexed or unstructured data sources, such as scanning raw log files or plain text for a specific keyword.
Implementation in C
#include <stdio.h>
// Linear search implementation
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // target found at index i
}
}
return -1; // target not found
}
int main() {
int arr[] = {5, 3, 8, 2, 9, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 9;
int result = linearSearch(arr, n, target);
if (result != -1) {
printf("Target %d found at index %d\n", target, result);
} else {
printf("Target %d not found in array\n", target);
}
return 0;
}
Sample Input and Output
Input: Array [5, 3, 8, 2, 9, 1], target = 9
Output: Target 9 found at index 4
Optimization Techniques
- I move frequently searched-for elements toward the front of the list over time (a technique called “move-to-front” or “transposition heuristic”) to reduce average search time for repeated queries on skewed access patterns.
- I use a sentinel value at the end of the array to eliminate the bounds check in the loop condition, slightly reducing the number of comparisons per iteration in performance-critical code.
- For repeated searches on the same static dataset, I switch to a more appropriate structure altogether — sorting once and using binary search, or building a hash table for O(1) average-case lookups.
- I parallelize the search across multiple threads or processing units when working with extremely large unsorted datasets, dividing the collection into chunks searched simultaneously.
Common Mistakes
- Using linear search on large, frequently searched datasets when a more efficient structure (sorted array with binary search, or a hash table) would be far more appropriate.
- Forgetting to include early termination, needlessly continuing to scan after a match has already been found.
- Off-by-one errors in the loop bounds, either missing the last element or reading one element past the end of the array.
- Assuming linear search takes advantage of sorted data — it does not, and using it on sorted data without switching to binary search wastes a clear opportunity for better performance.
- Not handling empty collections as an edge case, which can cause errors depending on how the loop and its bounds are implemented.
Further Reading
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, MIT Press: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Knuth, Donald E., The Art of Computer Programming, Volume 3: Sorting and Searching: https://www-cs-faculty.stanford.edu/~knuth/taocp.html
- GeeksforGeeks, “Linear Search”: https://www.geeksforgeeks.org/dsa/linear-search/
- Sedgewick, Robert and Wayne, Kevin, Algorithms, 4th Edition: https://algs4.cs.princeton.edu/home/
