Searching & Two Pointers · Comparison
Search and two-pointer techniques compared
Linear search, binary search, binary search on the answer, two pointers and sliding window: what each one requires and which problem shape it solves.
| Algorithm | Time | Space | Requires | Answers | Difficulty |
|---|---|---|---|---|---|
| Linear SearchLinear search | O(n) | O(1) | Nothing | Is x here, and where | Intro |
| Binary SearchBinary search | O(log n) | O(1) | Sorted, random access | Position of x, first position ≥ x | Intro |
| Binary Search on AnswerBinary search on the answer | O(n log R) | O(1) | Monotonic answer | Smallest or largest feasible value | Hard |
| Two PointersTwo pointers | O(n) | O(1) | Sorted, or ends that converge | Pairs, dedupe, partition | Intermediate |
| Sliding WindowSliding windows | O(n) | O(k) | Contiguous range, incrementally maintainable | Longest, shortest or count of subarrays | Intermediate |
When to pick which
Linear Search Linear search
Unsorted data, a single query, or tiny n. For repeated queries sort first or switch to a hash table.
Binary Search Binary search
Finding a value or a boundary (lower_bound) in a sorted array. Not on linked lists — there is no O(1) middle.
Binary Search on Answer Binary search on the answer
The question is 'the smallest x such that …' and feasibility is monotonic in x. Write check(x) and binary search over x.
Two Pointers Two pointers
Pair with sum k in a sorted array, in-place dedupe, partitioning into two classes. Each pointer moves one way, O(n) total.
Sliding Window Sliding windows
Longest or shortest contiguous subarray or substring meeting a condition. Right end grows, left end shrinks, and the window state updates in O(1).
Choosing guide
- Sorted + one value or boundary → binary search. Sorted + a pair → two pointers.
- The word 'contiguous' appears → sliding window. A subsequence (non-contiguous) is not a window; it is usually DP.
- Asks for the smallest or largest feasible value, not a position → binary search on the answer. Cues: 'minimum needed', 'maximum achievable', 'minimise the maximum'.
- The window condition cannot be updated in O(1) (window median, say) → sliding window alone is not enough; add a monotonic deque, a balanced tree or two heaps.
- Unsorted but queried often → not a search-algorithm problem: sort once (O(n log n)) or use a hash table (O(1) per query).