← Back to the searching page
Binary Search (and its many faces)
Halve a sorted range every step. The real skill is the variants: boundaries, rotated arrays, and searching the answer space itself.
What to know
- lower_bound/upper_bound find first ≥ and first > — most bugs are boundary bugs.
- Rotated arrays: one half is always sorted; recurse into the half that can contain the target.
- Binary search on the answer: guess a value, test feasibility, shrink — Koko eating bananas, split array.
- Use lo + (hi − lo) / 2 to dodge overflow in fixed-width languages.
In the wild: Database index seeks, git bisect, autoscaling threshold tuning, version-cutoff finding.
Algorithms to reach for
Classic binary search
O(log n)Membership in a sorted array (LeetCode 704)
Lower / upper bound
O(log n)First/last occurrence, insertion points (LeetCode 34)
Rotated-array search
O(log n)Search after unknown rotation (LeetCode 33)
Binary search on answer
O(n log range)Min capacity/speed satisfying a predicate (LeetCode 875, 410)
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.