Yosunnyvim
I say whatever I want, yeah, I do whatever I want, huh

Binary Search

Published on

Classic Binary Search

Search for value x in a sorted array.

int l = 0, r = n - 1;
bool found = false;
while (l <= r) {
    int m = (l + r) / 2;
    if (x == v[m]) { found = true; break; }
    else if (x > v[m]) l = m + 1;
    else r = m - 1;
}

O(log n) per query.

Problems using this

  • A. Binary Search

Lower Bound (Closest to the Left)

Find the first index where a[i] >= x (or equivalently, the index where x would be inserted to keep sorted order).

Use r = l + 1 termination (avoids infinite loop):

int l = -1, r = n;
while (r > l + 1) {
    int m = (l + r) / 2;
    if (x > v[m]) l = m;
    else r = m;
}
cout << r;   // first index where v[r] >= x

When x > v[m], answer is to the right of m → l = m. Otherwise answer is at or before m → r = m.

Problems using this

  • B. Closest to the Left

Upper Bound (Closest to the Right)

Find the first index where a[i] > x.

Same template, but compare with >= instead of >:

while (r > l + 1) {
    int m = (l + r) / 2;
    if (x >= v[m]) l = m;   // x is >= v[m], go right
    else r = m;
}
cout << r;   // first index where v[r] > x

Problems using this

  • C. Closest to the Right

Binary Search on Answer

When the answer is a number and we can check “is x valid?” with a good(x) function that is monotonic (if good(x) is true, then good(x-1) is also true — or the opposite).

We binary search on the answer space instead of the array.

Example: What’s the maximum number of hamburgers we can make?

bool good(ll m) {
    ll needB = max(0LL, freq[0] * m - b);
    ll needS = max(0LL, freq[1] * m - s);
    ll needC = max(0LL, freq[2] * m - c);
    ll cost = needB * cb + needS * cs + needC * cc;
    return money >= cost;
}

Find the range: start with l = 0, r = 1, double r until good(r) is false:

ll l = 0, r = 1;
while (good(r)) r *= 2;
while (r > l + 1) {
    ll m = (l + r) / 2;
    if (good(m)) l = m;
    else r = m;
}
cout << l;

Problems using this

  • H. Hamburgers — max hamburgers with limited ingredients
  • B. Ropes — max length such that k ropes can be cut
  • D. Children Holiday — max groups
  • G. Student Councils — max councils
  • A. Packing Rectangles — min container size

Binary Search on Doubles

When the answer is a real number (e.g. find x such that √x + x² >= c):

  1. Find upper bound by doubling until good(r) is true.
  2. Binary search with fixed iterations (100 is enough for precision):
double l = 0, r = 1;
while (!good(r)) r *= 2;
for (int i = 0; i < 100; i++) {
    double m = (r + l) / 2;
    if (good(m)) r = m;
    else l = m;
}
cout << fixed << setprecision(15) << r;

For doubles, use for (int i = 0; i < 100; i++) instead of while (l <= r) to avoid precision issues.

Problems using this

  • E. Equation — find x where √x + x² = c
  • B. Ropes — max rope piece length

Binary Search on Doubles (Maximize)

When we want the maximum valid value (e.g. max rope length):

double l = 0, r = 1e8;
for (int i = 0; i < 100; i++) {
    double m = (r + l) / 2;
    if (good(m)) l = m;    // m works, try bigger
    else r = m;
}
cout << l;

good(m) = can we cut at least k pieces of length m?

bool good(double x) {
    int s = 0;
    for (int i = 0; i < n; i++) s += floor(v[i] / x);
    return s >= k;
}

Problems using this

  • B. Ropes

When to Use Binary Search on Answer

Ask yourself:

  1. Is the answer a number (integer or real)?
  2. Can I write a good(x) function?
  3. Is it monotonic — if x works, does x-1 also work (or vice versa)?

If yes to all three → binary search on answer.

Common patterns:

  • “Maximum minimum” or “minimum maximum”
  • “Can we achieve X with these resources?”
  • “What’s the largest/smallest value such that condition holds?”
Back to top