Linear Search
Scenario
You are processing an endless, streaming log file of a production system and need to find the first occurrence of a specific system error.
The logs are ordered chronologically, not alphabetically by error type. How do you find the error without buffering the entire stream into memory to sort it?
Why it exists
Problem: Finding a specific element in an unsorted or dynamically streaming data structure requires checking elements until the target is found.
Naive approach: Load the entire dataset into memory, sort it in O(N log N) time, and then perform a fast binary search.
Better idea: Simply scan the data sequentially from left to right. This takes O(N) time but requires zero pre-processing overhead and works on endless streams or unstructured data.
Mental model
Like looking for a specific book on an unorganized shelf, you check the first book, then the second, and so on until you find it.
Iterate through the collection one element at a time. Compare the current element to the target. If it matches, return the index. If the loop finishes without a match, return a 'not found' indicator (like -1).
Repeated decision: Is `arr[i] == target`? If yes, stop. If no, advance to `i+1`.
Explanation
Linear search is the most fundamental retrieval algorithm. Its theoretical time complexity is O(N) in the worst case (the target is at the end or absent) and O(1) in the best case (the target is at index 0).
Despite its O(N) complexity, linear search is exceptionally fast on modern CPUs for small arrays (under ~100 elements). Because it accesses memory sequentially, the CPU's hardware prefetcher successfully anticipates future memory accesses, loading contiguous blocks (cache lines) into the L1 cache. This results in a near-zero cache miss rate.
The loop invariant is simple: at the start of the i-th iteration, the target value does not exist in any of the preceding elements from index 0 to i-1. When the loop terminates after checking all elements, this invariant proves the target is entirely absent from the array.
Linear search operates strictly in place with O(1) space complexity, making it ideal for memory-constrained environments like IoT firmware.
Key points
- Sequential Scanning: Checks every element one by one. Works on unsorted arrays, linked lists, and streams.
- Cache-Friendly: Sequential memory access allows hardware prefetchers to eliminate cache misses, making it extremely fast on small arrays.
- Zero Overhead: Requires no pre-processing (sorting) and O(1) auxiliary space.
Pattern: Sequential Scan
Recognition cues:
- The dataset is unsorted and small.
- The data is arriving as a continuous stream and cannot be buffered or sorted.
- You need to find all occurrences of a value (global linear search).
Failure signals
- You are running linear search repeatedly on a massive, static dataset. You should sort it once and use binary search, or use a Hash Map.
Engineering examples
Log Analysis
Finding the first occurrence of an error in an unsorted log file.
It processes the stream sequentially without needing to buffer or sort the data.
Embedded Systems
Finding a value on an IoT device with severe memory constraints.
It requires O(1) auxiliary space and avoids recursive call stacks.
When not to use
- Repeated queries on a large, static dataset: Doing M queries takes O(M * N) time. It is better to build a Hash Map (O(N) build, O(1) query) or sort and binary search (O(N log N) build, O(log N) query).
Common mistakes
- Returning inside the loop incorrectly: When doing a global linear search (finding all occurrences), returning on the first match terminates the loop prematurely. You must append to a list and return after the loop finishes.
Glossary
- theoretical time complexity
- The mathematical prediction of how long an algorithm will take in the absolute worst-case scenario.
- memory-constrained environments
- Systems with very little available storage or RAM, like smart home devices or microchips.
- IoT firmware
- The permanent software programmed directly into small, embedded internet-connected devices.
Recall questions
- Why might linear search outperform binary search on a very small array (e.g., 20 elements)?
- What is the loop invariant of linear search?
- When is linear search the only viable option?
Questions & answers
Implement a standard linear search.
Loop through the array with an index `i`. If `arr[i] == target`, return `i`. If the loop finishes, return `-1`.
Approach: Sequential scan.
Find the maximum element in an unsorted array.
Initialize `max_val` to the first element. Perform a linear scan. If the current element is greater than `max_val`, update `max_val`. Return `max_val` after the loop.
Approach: Linear scan for extremum.
Continue learning
Previous: Iteration & Traversal
Next: Binary Search
Related: Binary Search