5 patterns · 23 problems
Binary Search
Halve the search space every step — on sorted arrays, and on answers, ranges, and allocations.
Each pattern below starts with when to reach for it and the clue in the prompt that gives it away. Then it runs on real problems: pick one to watch the technique step by step, open its full solution, or practise it on an original problem with graded tests.
01Pattern
Basic Binary Search
Halve a sorted interval until the target appears.
O(log n)naïve O(n)When to reach for it
- Involves searching for a target element in a sorted array by repeatedly dividing the search interval in half.
Spot it in the prompt
Look for scenarios where the array is sorted, and you need to find a specific element efficiently.
Search Insert Position
How to solve it
Binary search for the target; when absent, the final low pointer marks the index where it should be inserted.
Threshold Insert Slot is our own problem on the same technique: a new statement, graded in your browser.
02Pattern
Range Search
Binary search the answer, not the array.
O(n log(range))When to reach for it
- Involves searching for the maximum or minimum value that satisfies a specific condition within a given range.
Spot it in the prompt
Look for scenarios where you need to optimize a value within a given range, such as maximizing or minimizing a certain condition.
Split Array Largest Sum
How to solve it
Animation shows the Range Search techniqueBinary search the largest allowed subarray sum; greedily count required splits to test feasibility at each guess.
Balanced Truckloads is our own problem on the same technique: a new statement, graded in your browser.
03Pattern
Allocation Problems
Search the smallest max that a greedy split allows.
O(n log(range))When to reach for it
- Involves dividing resources or items among multiple entities while optimizing a certain criterion.
Spot it in the prompt
Look for scenarios where resources need to be distributed among entities with certain constraints, and the goal is to optimize a certain criterion, such as minimizing the maximum or maximizing the minimum.
Koko Eating Bananas
How to solve it
Animation shows the Allocation Problems techniqueBinary search the eating speed; for each candidate rate sum the hours needed and shrink toward the smallest rate that still finishes in time.
Overnight Print Rate is our own problem on the same technique: a new statement, graded in your browser.
04Pattern
Counting Occurrences
Find boundaries with binary search, then subtract indices.
O(log n)naïve O(n)When to reach for it
- Involves counting the number of occurrences of a specific value or satisfying a certain condition.
Spot it in the prompt
Look for scenarios where you need to count occurrences or determine the frequency of certain elements/values in a sorted array or range.
Find First and Last Position of Element in Sorted Array
How to solve it
Animation shows the Counting Occurrences techniqueRun two binary searches for the leftmost and rightmost target indices; their difference gives the occurrence range.
Deviation Value Span is our own problem on the same technique: a new statement, graded in your browser.
05Pattern
Bitonic Array Search
Follow the slope to the peak in log time.
O(log n)naïve O(n)When to reach for it
- Involves searching for an element in a bitonic array, which first increases and then decreases (or vice versa).
Spot it in the prompt
Look for scenarios where the array exhibits a bitonic behavior, and you need to find an element within it efficiently.
Find Peak Element
How to solve it
Animation shows the Bitonic Array Search techniqueBinary search toward the higher neighbor since that side is guaranteed to contain a peak element.
Survey Line Crest is our own problem on the same technique: a new statement, graded in your browser.
After the pattern
Now solve one you haven't seen.
Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.
1,194 problems · 15,062 graded tests · free