First PrinciplesStart anywhere. Prove it, then move on.

Rung 27

Sorting and searching under constraint

Real problems, with a time and space budget.

Best attempted after 18. Arrays, lists, dicts, and Big O and 26. Trees and heaps. Nothing stops you trying this now — the gate will tell you if you were right.

The gate

Implement binary search correctly and prove it with a randomised test against a brute-force scan over thousands of cases, including empty input, a single element, the value absent, and duplicates. Then solve a set of constrained problems, stating the time and space complexity of each before submitting it.

Nobody checks this but you. Do it honestly and the rungs above hold; do it loosely and they will not, somewhere further up where the cause is much harder to find.

Everything so far has asked whether your code is correct. This rung adds a second question that will not go away: is it fast enough, in the memory available?

That constraint changes how you think. A correct solution that exceeds the time limit scores nothing, and the fix is rarely micro-optimisation — it is a different algorithm, usually reached by noticing which rung-18 structure the problem is secretly about.

Why this is on the ladder

Because it is the first rung where the answer is not "does it work" but "what did it cost", and every rung above cares about cost. It also builds the habit of stating complexity before running the code — a prediction you can be wrong about, which is what makes it worth making.

Do this

Start with binary search, which is famously easy to get subtly wrong. Write it, then test it properly: generate thousands of random sorted arrays and random targets, and compare your result against a linear scan every time. Include the empty array, a single element, a target below everything, a target above everything, and duplicates.

Randomised testing against a slow-but-obviously-correct reference is the most valuable technique on this rung. It finds the boundary case you did not think of, which is by definition the one you cannot find by thinking.

Then work problems from the CSES set or USACO training, and for each one write down your predicted complexity before you submit. When something is too slow, ask what structure the problem wants rather than how to shave constants.

LeetCode is the other well-known source of these problems, and works fine for this if you prefer it.

Where people get stuck

The classic binary search bug is the loop boundary — < against <=, or a midpoint that fails to shrink the range and loops forever. This is not carelessness; it is genuinely delicate, and the reason the gate asks for a randomised comparison instead of a few hand-picked cases.

The other trap is optimising a solution whose complexity is wrong. Halving the constant on an O(n²) routine still loses to an O(n log n) one at any interesting size. Fix the exponent before the constant.

Reading