Binary search finds a target, or the point where a condition flips from false to true, by halving the range it still has to check, so a million items take about twenty steps. It works on sorted arrays and, more usefully in interviews, on any space of possible answers where a yes or no question flips exactly once.
Pattern 5 of 16 in coding patterns · Searching and linking
When to reach for it
- The input is sorted, or sorted and rotated, and you need a position.
- You need the first or last element that satisfies a condition.
- The question asks for the smallest or largest value of something you could check quickly for a guess.
- n is large and a linear scan per query is too slow.
The core idea
Keep a range that is guaranteed to contain the answer. Look at the middle, decide which half cannot contain it, and drop that half. When the range is down to one point, that point is the answer.
The robust way to think about it is a predicate: a function ok(x) that is false for small x and true for large x. Binary search finds the first x where it turns true. Searching a sorted array is the special case ok(i) = nums[i] >= target. Searching an answer space is the same loop with a different ok: for example, "can a daily quota of q clear the backlog in time?" is false for small quotas and true for large ones.
A Python template
def first_true(lo, hi, ok):
"""Smallest x in [lo, hi] where ok(x) is True, or hi + 1 if there is none.
ok must be False for every x before the answer and True after it."""
while lo <= hi:
mid = (lo + hi) // 2
if ok(mid):
hi = mid - 1 # mid works: look for an earlier one
else:
lo = mid + 1 # mid fails: the answer is after it
return lo
def lower_bound(nums, target):
"""Index of the first value >= target, or len(nums) if there is none."""
return first_true(0, len(nums) - 1, lambda i: nums[i] >= target)
def min_daily_quota(file_sizes, days):
"""Smallest daily upload quota that clears the files, in order, in time."""
def clears(quota):
used, today = 1, 0
for size in file_sizes:
if today + size > quota:
used, today = used + 1, 0 # start a new day
today += size
return used <= days
return first_true(max(file_sizes), sum(file_sizes), clears)Time and space
Each step halves the range: O(log n) comparisons and O(1) extra space. Searching an answer space costs O(log R) checks, where R is the size of the range of possible answers, times the cost of one check. For the quota example that is O(n log R).
Common mistakes
- Mixing range conventions (
lo <= hiwithhi = mid) and looping forever. - Using a predicate that does not flip exactly once, so halving throws the answer away.
- Returning on the first match when the question wants the first or last of several equal values.
- Starting the answer space at the wrong place, such as a quota of 0 instead of the largest single file.
- In Java or C++, computing the middle as
(lo + hi) / 2, which can overflow; writelo + (hi - lo) / 2.
How to explain it out loud
Lead with the predicate: "For a quota q I can check in O(n) whether it clears the files in time, and if q works, anything larger works too. So I can binary search q." Naming the yes or no question and why it flips once is the insight interviewers are probing for when they ask how you knew binary search applied.
Then state what the range always contains, trace three steps on a tiny input, and say what you return when nothing works. Walking through the boundary handling before you are asked is what turns a correct answer into a convincing one, and it is exactly the reasoning Devana's logic explanation metric listens for.
Practice questions
These come from Devana's question bank, in the order to try them. Each one starts a voice mock interview with Josh, Devana's AI interviewer, on that question, so you practice explaining the approach out loud as well as getting it right.