guest@itl:~/home/binary-search$
templates/binary-search-on-answer.cpp
compilable
$cat templates/binary-search-on-answer

Binary Search on Answer

Search for the optimal value satisfying a monotonic predicate in O(log n).

[Binary Search]|
Jul 9, 2026
|explanatory_notes.md|
#binary-search#predicate#optimization#monotonic
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool check(ll mid) {
  // return true if mid is a feasible answer
  return true;
}

ll bsOnAnswer(ll lo, ll hi) {
  ll ans = -1;
  while (lo <= hi) {
    ll mid = lo + (hi - lo) / 2;
    if (check(mid)) {
      ans = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  return ans;
}
22 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

Binary Search on Answer

Applies binary search to optimization problems with a monotonic predicate P(x)P(x): if P(x)P(x) is true, then P(y)P(y) is true for all y≥xy \ge x (or vice versa).

How It Works

  • Define a check(mid) function that returns true if mid is a feasible answer

  • Binary search narrows [lo,hi][lo, hi] to find the smallest (or largest) feasible value

  • If check(mid) passes, move the boundary inward; otherwise, move outward

    • Template

  • For minimization: find smallest xx where check(x) is true → hi = mid

  • For maximization: find largest xx where check(x) is true → lo = mid

    • When to Use

  • "What is the minimum/maximum value such that..."

  • Feasibility is monotonic in the answer

  • Classic examples: minimum time, maximum distance, minimum cost

    • Complexity

  • Time — O(log⁡(range)⋅T(check))O(\log(\text{range}) \cdot T(\text{check}))

  • Space — O(1)O(1) + check function space