Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 63 ยท Search and Greedy Thinking

Binary Search on Answer for Contests

Contest guide to binary search on the answer: monotonic checks, first-true and last-true templates, scaled integers for real answers, and the bounds bugs that cost penalties.

In a contest, a problem that says "find the largest X such that..." or "find the smallest time in which..." is very often a binary search in disguise. You do not search an array. You search the range of possible answers, and for each guess you answer one yes/no question: "is this guess good enough?" The idea itself is covered in Binary Search on the Answer; this lesson is the contest version, where speed of writing and freedom from off-by-one mistakes matter as much as the idea.

The plan is simple. You will keep two tiny templates in your toolbox, learn to spot the monotonic structure in a statement, handle real-valued answers without floating-point surprises, and finish with the list of bounds bugs that cause most wrong answers on this topic.

Spotting the pattern

Binary search on the answer applies when three things hold:

  1. The answer is a number in a known range, such as the length of a rope piece or the number of days.
  2. There is a check function ok(x) that you can evaluate in about O(n) time.
  3. The check is monotonic: if ok(x) is true, then it is true for every easier value (or the other way round).

Statements often hint at this with wording such as "maximize the minimum", "minimize the maximum", "the smallest number of days so that", or "at least k pieces of length x". A typical constraint is an answer up to 10^9 or 10^18 with n around 10^5. A linear scan over answers is far too slow, but 30 to 60 halvings times an O(n) check is fast.

flowchart LR
    A["Read statement"] --> B["Answer is a number in a range?"]
    B --> C["Can I check one value in O(n)?"]
    C --> D["Is the check monotonic?"]
    D --> E["Binary search the boundary"]

The three questions to ask before reaching for binary search.

Two templates, written once

Most mistakes come from rewriting the loop under pressure and mixing the lower and upper midpoint. Write the loop once, for the "first true" case, and derive the other case from it.

Python first_true and last_true templates

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the sentinel results. first_true returns hi + 1 when nothing is true and last_true returns lo - 1. In a contest that is exactly what you want: you can test the result against the sentinel and print -1 or impossible as the statement demands.

Always say the direction in a comment: "False then True" or "True then False". If you cannot write that sentence, the check is probably not monotonic and binary search will not work.

Choosing the bounds

The loop is easy; the bounds are where contestants lose points. Use these habits:

  • The lower bound must be a value the answer can actually take, or a safe value that the check handles. A rope length of 0 would divide by zero, so start at 1.
  • The upper bound must be at least as large as the true answer. Being too large only costs one or two extra halvings. Being too small silently gives the wrong answer.
  • When unsure, take a big safe bound such as 10**18. Python integers do not overflow, and 60 halvings are cheap.
  • Test both ends: the smallest possible input and the largest.

Real-valued answers

When the answer is a real number, you have two safe choices. The first is a fixed number of iterations: 60 to 100 halvings shrink any realistic range far below floating-point precision, and the loop cannot hang. Do not write while hi - lo > 1e-9 when the range is huge, because at large magnitudes the doubles near lo and hi can be further apart than your epsilon and the loop never ends.

The second choice, and often the better one, is to scale to integers. If the statement wants two decimal places, multiply every length by 100 and search integers. Then there is no rounding at all, and "truncate to two decimals" is exactly what the integer answer means.

Python Real answers: floats versus scaled integers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The float search converges to about 2.005, and both versions print 2.00 here. That agreement is partly luck: a float answer sitting just below a boundary such as 2.005 can be rounded by :.2f to a value that fails the check, and floating-point error can nudge it either way. The integer version states the rule "largest length in whole centimeters" directly, so prefer it whenever the required precision is a fixed number of digits.

Bounds bugs and the monotonic trap

Two classic failures are worth seeing once. The first is the infinite loop when you search for the largest good value with lo = mid but compute the lower midpoint. With lo = 3, hi = 4, the midpoint is 3, lo stays 3, and the loop never ends. Either use the upper midpoint (lo + hi + 1) // 2, or use the last_true wrapper above, which never has this problem.

The second is checking a non-monotonic predicate. If ok flips more than once, the search lands on some boundary, not necessarily the one you wanted, and passes samples by luck.

Python also has a built-in way to search a range: since Python 3.10, bisect accepts a key, and range objects support indexing without being built in memory.

Python bisect over a range, plus a non-monotonic trap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last two lines show why proving monotonicity matters. The search returns 20, skipping the block 4 to 6 completely, and a different range could return a different boundary. Always argue in one sentence why a larger (or smaller) value can only make the check easier.

Putting it together on a contest problem

Here is the habit to apply on every such problem:

  1. Write the check as a standalone function and test it by hand on the sample.
  2. State the direction of monotonicity.
  3. Pick lo and hi generously and handle the "impossible" sentinel.
  4. Count the total cost: about log2(range) checks, each O(n). For n = 2 * 10^5 and a range up to 10^18 that is roughly 60 * 2 * 10^5 = 1.2 * 10^7 steps, which is fine in Python only if the check is a tight loop or a generator expression.
  5. Stress test the search against a linear scan over small ranges (see Stress Testing with a Brute Force in the toolkit chapter).

Ternary search on unimodal functions

Binary search needs a yes/no predicate that flips once. Some problems instead give a function that rises and then falls (or falls and then rises) and ask for its peak: the price that maximizes profit, the meeting point that minimizes total walking distance, the angle that maximizes a shadow. Such a function is unimodal, and the tool for it is ternary search.

Pick two probe points m1 < m2 inside the interval. If you are maximizing and f(m1) < f(m2), the peak cannot be left of m1, so discard the left third. Otherwise it cannot be right of m2, so discard the right third. Each round keeps two thirds of the interval and costs two evaluations.

Two conditions must hold, and both are the usual source of wrong answers:

  • The function must be strictly unimodal on the interval. A flat stretch (a plateau) before or after the peak makes the comparison f(m1) < f(m2) uninformative, because equal values do not tell you which side holds the peak.
  • A convex function (for minimizing) or a concave function (for maximizing) always qualifies. Sums of convex functions are convex, which is why "sum of distances" problems work.

For integer domains there is a simpler alternative that avoids the plateau trouble when the function is strictly unimodal: run ordinary binary search on the slope. Test whether f(mid) < f(mid + 1). If yes, the peak is to the right; otherwise mid could be the peak or it is to the left. This needs one comparison per round and finishes in about log2 of the range. For real domains, loop a fixed number of rounds (about 100 for a range of 10^9 and a precision of 10^-9) instead of testing hi - lo < eps, which is fragile with floating-point numbers.

The golden-section search is a refinement that reuses one of the two probe points from the previous round, so it needs one new evaluation per round instead of two. It shrinks the interval by the factor 0.618 each round. It matters only when evaluating f is expensive.

Python Integer and real ternary search, golden section

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The grid search at the end is the honest check for any real-valued answer: if a coarse brute force lands in the same place, the search is probably right.

Where unimodal functions come from

Three situations produce a function you can search with ternary search or with binary search on the slope.

  • A quadratic. a x^2 + b x + c is convex when a > 0 and concave when a < 0, so its extreme value on an interval can be searched. (It also has a closed form, x = -b / 2a, which is a good check.) Many "choose the best price/speed/angle" problems have a profit that is a quadratic or a sum of convex pieces.
  • A bitonic sequence, an array that strictly increases up to a peak and then strictly decreases. Finding the peak needs no ternary search: binary search on the sign of a[mid + 1] - a[mid], as in the loop below. If the sequence can contain equal neighbours, the slope test is not informative and you may have to scan.
  • A convex or concave function of a real parameter: the sum of distances from a point to a set of points, the maximum of several linear functions, the time to finish a task as a function of speed. Sums and maxima of convex functions stay convex, so the search is valid.
Python Quadratic extremum, bitonic peak, best meeting point

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which condition must the check function satisfy for binary search on the answer to work?

    Binary search discards half of the range after each check. That is only safe when the results form one boundary between a False block and a True block.
  2. 2. You maximize a value with the update lo = mid. Which midpoint avoids an infinite loop?

    With lo = mid and the lower midpoint, a range such as [3, 4] never shrinks. The upper midpoint always moves lo forward or hi down.
  3. 3. An answer needs exactly two decimal places. What is the most robust approach?

    Scaling removes floating-point error entirely. An epsilon loop on a huge range can hang because neighboring doubles may be further apart than the epsilon.
  4. 4. What should last_true(lo, hi, ok) return when no value in the range satisfies ok?

    Because last_true is first_true on the negated check minus one, it returns lo - 1 when every value fails, which the caller can turn into -1 or 'impossible'.

Summary

  • Search the range of answers when a yes/no check on a candidate is monotonic and cheap.

  • Keep one tested first_true template and derive last_true from it, so you never re-derive the midpoint.

  • State the direction of the check in a comment, and choose generous but safe bounds.

  • For real answers use a fixed iteration count, or better, scale to integers so there is no rounding.

  • Watch for the lower-midpoint infinite loop, sentinel results, and non-monotonic checks.

  • Total cost is the number of halvings (about log2 of the range) times the cost of one check.

  • For a function that rises then falls, use ternary search (or binary search on the slope for integers); it needs strict unimodality.

Next: Two Pointers and Sliding Windows in Practice