Binary Search for Competitive Programming

Few algorithms reward clear thinking like binary search: a handful of lines that turn an O(n) scan into an O(log n) search and rescue solutions from the dreaded "Time Limit Exceeded" verdict.

If your child is climbing toward contests like the USA Computing Olympiad, binary search is one of the first techniques worth mastering. It appears constantly, it is fast to implement, and it teaches a habit that strong competitors rely on everywhere: spotting structure in a problem and exploiting it. At BIAA, we treat it as a foundational tool in our competitive programming track.

The Core Idea: Searching a Sorted, Monotonic Space

Classic binary search finds a value in a sorted array. You keep a low and high boundary, look at the middle element, and discard the half that cannot contain your target. Each step halves the search space, so finding an answer among a million elements takes only about twenty comparisons.

The deeper insight that separates contestants is this: binary search does not really require an array. It works on any monotonic predicate — a yes/no question whose answer flips exactly once as you move across an ordered range. If a candidate value works, everything on one side of it also works; if it fails, everything on the other side fails too. That single flip is the boundary binary search hunts for.

Whenever a problem asks for the smallest value that works, or the largest value that still fits, ask whether feasibility is monotonic. If it is, binary search is usually the path.

Binary Search on the Answer

This is the pattern that wins the most contest problems, yet beginners rarely recognize it. Instead of searching through data, you search through possible answers.

Suppose a task asks for the minimum capacity needed so a delivery can finish within a deadline. Directly computing that capacity may be hard. But checking a single guess — "with capacity X, can we finish in time?" — is often easy with a greedy sweep or a quick simulation. And feasibility is monotonic: if capacity X works, any larger capacity works too. So you binary search over the range of possible capacities and run your feasibility check at each midpoint.

The recipe is reliable:

1. Identify the numeric answer space (it can be integers or real numbers).
2. Write a check(x) function returning true or false, fast enough to call repeatedly.
3. Confirm check is monotonic across that space.
4. Binary search for the boundary where the answer changes.

This decomposition — "guess, then verify" — also appears in olympiad math, where bounding an answer and proving feasibility is a standard strategy.

Use the Library, Then Learn the Bugs

In C++, the Standard Template Library already provides battle-tested helpers. lower_bound returns the first position where an element is greater than or equal to a target; upper_bound returns the first position strictly greater; and binary_search simply reports presence. Reaching for these first avoids many self-inflicted errors and is faster to write under contest pressure.

When you must hand-write the loop — which you will for binary search on the answer — three bugs cause most failed hidden tests:

• Overflow in the midpoint. Writing mid = (low + high) / 2 can overflow fixed-size integers. This was a real defect in Java's standard library, undetected for years and fixed in 2006. Prefer mid = low + (high - low) / 2.
• Infinite loops. Updating boundaries inconsistently — for example, setting high = mid when your invariant expects mid - 1 — can stall the loop forever.
• Off-by-one errors. Mixing up while (low < high) and while (low <= high) can silently skip the first or last element.

How to Practice

Start with plain sorted-array searches, then graduate to "minimize the maximum" and "maximize the minimum" problems, which are almost always binary search on the answer in disguise. Solve a handful, then revisit your fastest-failing submissions to spot the boundary patterns you missed. Reading editorials after an honest attempt teaches the recognition skill more than reading them cold.

Note that contest formats, divisions, and eligibility differ by competition and change over time, so always confirm current details on each contest's official site before registering.

Ready to turn pattern recognition into ranked results? Explore BIAA's competitive programming program to build these skills with structured practice and mentorship.