Searching
Linear Search
Checks every element from left to right until the target is found or the array ends. Works on unsorted data.
1Detailed explanation
Linear search checks each element in order until it finds the target or reaches the end. It needs no preparation and works on unsorted data, linked lists and streams.
Its cost grows linearly with the input: doubling the data doubles the worst-case work. For repeated searches on large static data, sorting once and using binary search, or building a hash set, is usually better.
2Pseudocode
procedure linearSearch(A, target)
for i ← 0 to length(A) − 1
if A[i] = target
return i
return −13Interactive visualization
Checks every element from left to right until the target is found or the array ends. Works on unsorted data.
4Implementations
Equivalent implementations in four languages — the same code the visualizer highlights line by line. Each is a complete program.
5Time and space complexity
Time: Best case: the target is the first element (1 comparison). Worst case: the target is last or absent, so all n elements are compared. On average about n/2 comparisons → O(n).
Space: Only the loop index i is stored → O(1) auxiliary space.
6Common interview variations
- Return every index where the target occurs.
- Find the first and last occurrence in one pass.
- Sentinel linear search (avoids the bounds check in the loop).
- Search in a 2-D matrix row by row.