Binary Search · Theory
Read this before the problems
Binary search is usually taught as a trick for finding a number in a sorted array. That description is too small, and it is the reason people can write the array version from memory and still freeze on anything else. What follows builds the idea from its actual foundation, which is an invariant, and then shows why the same machine solves problems that contain no array at all.
The invariant is the whole idea
Every binary search maintains a range of candidates and one promise about it: if an answer exists, it is inside this range. Nothing else about the algorithm is fundamental. The comparisons, the arithmetic for the midpoint, the exact loop condition, all of it exists only to keep that promise true while making the range smaller.
This is why the algorithm is correct rather than merely plausible. When the loop ends because the range is empty, you have not failed to find the answer, you have proved there was none. The promise said any answer would be inside the range, and the range now holds nothing.
It is also why the classic bugs are bugs. If you set lo to mid instead of mid + 1, the range stops shrinking and the loop runs forever. If you set lo to mid + 2, the range shrinks too aggressively and can step over the answer, breaking the promise. State the invariant first and both mistakes become visible before you run anything.
Why halving gives you a logarithm
If each step discards half of the remaining candidates, the size of the range follows n, then n over 2, then n over 4, and so on. The number of steps before the range is empty is the number of times you can halve n before reaching 1, and that count is the base-two logarithm of n.
The practical consequence is worth carrying around as a number. A billion elements is about thirty steps. A trillion is about forty. This is why an interviewer who says the input can be enormous is often telling you the intended solution is logarithmic, without saying so directly.
The same reasoning explains the cost when each step does real work. In the Koko problem every candidate speed requires a pass over the piles, so the total is the number of halvings multiplied by the cost of one check. Binary search reduces how many times you check, never how expensive a single check is.
Sorted is a special case of monotonic
The requirement is not really that the input is sorted. The requirement is that the yes-or-no question you ask at a position changes its answer at most once as you move along the range. A sorted array satisfies this for the question "is this element at least the target", because once that becomes true it stays true.
Stating it that way opens up every problem that has no array in it. "What is the smallest eating speed that finishes in time" works because a speed that is fast enough stays fast enough when you increase it. "What is the smallest capacity that fits the load" works for the same reason. In each case you binary search the range of possible answers and use a feasibility check in place of an array lookup.
So the question to ask when you suspect this pattern is not "is something sorted here". It is "if I guess an answer, can I check it, and does the check flip from no to yes exactly once". If both hold, binary search applies, and the search space is the answers themselves.
Three templates, and really only two
Template A is the exact match. The range is closed at both ends, the loop runs while lo is at most hi, and you return as soon as the middle equals the target. Use it when the question is whether a specific value is present.
Template B finds a boundary. The loop runs while lo is strictly less than hi, the successful branch keeps the midpoint by assigning hi = mid, and the answer is whatever lo holds when the range collapses. Use it when the question is for the first or last thing satisfying some condition, which includes every lower bound and upper bound.
Template C searches the answers rather than the input, and structurally it is Template B with the array lookup replaced by a feasibility function. That is why the third template is not really a third thing to memorise. Learn the boundary shape properly and you get answer-space search almost for free.
The reason to name the template out loud in an interview is not ceremony. Saying "this is a boundary search, so the loop is lo < hi and I keep mid on success" commits you to a consistent set of details, and most binary search bugs come from mixing details across templates rather than from misunderstanding the problem.
Where it actually goes wrong
Almost nobody gets binary search wrong because they misunderstand halving. The failures cluster in four places, and they are worth rehearsing until they are boring.
The first is the loop condition. Closed ranges need lo <= hi, and boundary searches need lo < hi. Using the wrong one either skips a single-element range or spins forever. The second is the update. In Template A you must move past the midpoint with mid + 1 or mid - 1, and in Template B the keeping branch must assign hi = mid without subtracting, because the midpoint is still a live candidate.
The third is overflow, which matters in languages with fixed-width integers. Compute the midpoint as lo + (hi - lo) / 2 rather than (lo + hi) / 2. In Python this cannot happen and in JavaScript it will not happen at realistic sizes, but interviewers still ask, so know why the safer form exists.
The fourth is duplicates. Several of these problems assume distinct values, and the guarantees change when that assumption is dropped. Finding the minimum of a rotated array is logarithmic with distinct values and degrades to linear in the worst case when ties are allowed. Notice which assumption you are relying on, and say so.
Now work the problems
The seven problems below are ordered so that each one adds a single new idea to the one before it. Read the theory once, then work them in order rather than picking the interesting-looking ones.
Your notes
Which part of this did not click on the first read? Put it in your own words.