About Linear Search
Linear Search is the simplest way to find a value in a collection: examine each element in turn until the target is found or the array is exhausted. Unlike Binary Search it does not require the array to be sorted, which makes it the go-to method for unsorted data, linked lists, and small inputs. Its O(n) time is the cost of that generality — every element may need to be checked in the worst case.
Complexity Analysis
- Time Complexity
- O(n)
- Space Complexity
- O(1)
- Difficulty
- beginner
Key Concepts
No Sorting Required
Linear Search works on any array, sorted or not. This is its key advantage over Binary Search, which only works on sorted data.
First Match Wins
The scan returns the index of the first element equal to the target. If duplicates exist, later occurrences are never reached.
Worst and Best Cases
Best case is O(1) when the target is the first element; worst case is O(n) when the target is last or absent, requiring every element to be checked.
Common Pitfalls
Using it on large sorted data
If the data is already sorted and large, Binary Search's O(log n) is dramatically faster. Reach for Linear Search only when the data is unsorted or small.
Forgetting the not-found case
A correct implementation must return a sentinel (like -1) when the loop finishes without a match, rather than falling through with an undefined result.