Binary Search
Halve the search space every step. Works on any monotonic predicate, not just sorted arrays.
Newinterview weight 8022 problems2 visualisers
18
mastery
Attempts logged
0
Predicted success on the next one
33%
Solved here
0 / 22
What you actually need to hold in your head
- Search on the answer, not the array
- Find the boundary where the predicate flips
- Off-by-one lives in the lo, hi and mid updates
- Thirty steps is enough for a billion elements
Watch it run
Step through the algorithm before you write it.
Binary SearchE
Halve the search space each step by comparing the target to the midpoint of a sorted range.
O(log n)
Binary Search on the AnswerM
Koko eating bananas. The array is not sorted, but feasibility is monotonic in the eating speed, so binary search the speed instead of the array.
O(n log maxPile)
Patterns in this topic
The trigger phrases are what you are training yourself to notice.
Classic Binary SearchO(log n)
Maintain a half-open range and discard half of it each step based on a comparison with the midpoint.
sorted inputfind target or insertion point
Binary Search on the AnswerO(n log(range))
Guess an answer, check feasibility in linear time, and binary search over the monotonic feasible range.
minimise the maximummaximise the minimum
Binary Search problems
Ordered by sheet phase, so the early ones are the highest signal.
0 / 22 solved