Pattern 08 of 22
Binary Search Pattern: Template + 254 LeetCode Problems
Halve the search space each step — over an array, or over the answer itself.
- Easy
- 31
- Medium
- 138
- Hard
- 85
- Time
- O(log n)
What the binary search pattern is
Binary search needs a sorted array far less than it needs a monotone predicate — some property that is false for every candidate below a threshold and true for every candidate above it. Once you can write that predicate, you can bisect anything, including a range of possible answers that is nowhere stored in memory: guess a capacity, ask whether the shipment fits, and move the bound. Most binary search bugs are off-by-one errors in the exit condition, and the cure is to stop searching for a value and search for a boundary instead. Keep the loop as `while lo < hi`, never write `mid - 1` on the side you are keeping, and let the loop end when the two bounds meet — the survivor is the smallest input for which the predicate holds. That single shape covers first occurrence, last occurrence, insertion point and minimum feasible answer, so there is only one template to remember and it terminates by construction.
When to use it
- The array is sorted, or rotated-sorted, and you want a position rather than a scan.
- The answer is a number in a known range and checking a candidate is cheaper than finding it.
- The phrase "minimum largest", "maximum smallest", or "minimise the maximum" appears in the statement.
- A brute force over the answer range would work but is one order too slow.
The binary search template in Python
The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 254 problems listed below.
def smallest_feasible(low, high, feasible):
"""Smallest x in [low, high] with feasible(x) true, assuming it is monotone."""
while low < high:
mid = low + (high - low) // 2 # floor: biases toward low, never overflows
if feasible(mid):
high = mid # mid works, so the answer is mid or lower
else:
low = mid + 1 # mid fails, so the answer is strictly higher
return lowComplexity characteristics
- Time
- O(log n)
- Auxiliary space
- O(1)
Every iteration discards half of what is left, so the loop runs log₂ n times. When the search is over a range of possible answers rather than over an array, the cost is O(log W) iterations times whatever the feasibility check costs, where W is the width of the range — that product is the figure to quote, because the check is usually a linear scan and the real complexity is O(n log W). The iterative form uses constant space.
Eyes only
Meet the binary search problem you did not practise.
In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.
All 254 binary search LeetCode problems
Every problem in the library the binary search pattern applies to, grouped by LeetCode's own difficulty rating. 213 of the 254 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.
Related LeetCode topics
Easy (31)
Medium (138)
Hard (85)
Binary Search pattern FAQ
What is the binary search pattern?
Binary search needs a sorted array far less than it needs a monotone predicate — some property that is false for every candidate below a threshold and true for every candidate above it.
How many LeetCode problems use the binary search pattern?
This page lists 254 LeetCode problems that the binary search pattern applies to: 31 Easy, 138 Medium and 85 Hard. 213 of them carry a complete Python solution with complexity analysis.
What is the time complexity of the binary search pattern?
O(log n) time and O(1) space. Every iteration discards half of what is left, so the loop runs log₂ n times. When the search is over a range of possible answers rather than over an array, the cost is O(log W) iterations times whatever the feasibility check costs, where W is the width of the range — that product is the figure to quote, because the check is usually a linear scan and the real complexity is O(n log W). The iterative form uses constant space.
When should I use the binary search pattern in an interview?
The array is sorted, or rotated-sorted, and you want a position rather than a scan. The answer is a number in a known range and checking a candidate is cheaper than finding it.
Which binary search problem should I start with?
LeetCode 35. Search Insert Position is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.
What patterns are related to binary search?
Two Pointers, Sorting, Greedy, Heap / Priority Queue. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.
More ways in: all 22 patterns, the curated study lists, or the full problem list.