Binary Search is one of the most useful techniques in competitive programming.

Most beginners learn it as an algorithm to search for an element in a sorted array. But on Codeforces, Binary Search is often used in a much more powerful way:

Instead of searching for an element, we can search for the answer.

This idea is commonly called Binary Search on Answer.

In this blog, I will explain both approaches with simple examples.

1. Basic Binary Search

Suppose we have a sorted array:

1 3 5 7 9 11 15

and we want to find whether 9 exists.

Instead of checking every element, Binary Search repeatedly divides the search space into two halves.

Initially:

[1 3 5 7 9 11 15]

Middle element:

7

Since:

9 > 7

we ignore the left half.

Now:

[9 11 15]

The middle element is 11.

Since:

9 < 11

we search the left part.

We find 9.

Therefore, instead of checking N elements, we only need approximately:

log₂(N)

comparisons.

Complexity

Time:  O(log N)
Space: O(1)

2. Standard Implementation

A common implementation is:

int binarySearch(vector<int>& a, int target) {
    int l = 0;
    int r = a.size() - 1;

    while(l <= r) {
        int mid = l + (r - l) / 2;

        if(a[mid] == target)
            return mid;

        if(a[mid] < target)
            l = mid + 1;
        else
            r = mid - 1;
    }

    return -1;
}

One small but important detail is:

int mid = l + (r - l) / 2;

instead of:

int mid = (l + r) / 2;

The first form avoids integer overflow when l and r are very large.

3. Lower Bound and Upper Bound

In competitive programming, we often don't simply want to know whether an element exists.

We may want to find its position.

Lower Bound

lower_bound finds the first position where:

a[i] >= x

Example:

Array:
1 2 2 2 5 7

x = 2

The lower bound is the first 2.

int pos = lower_bound(a.begin(), a.end(), x) - a.begin();

Upper Bound

upper_bound finds the first position where:

a[i] > x

For:

1 2 2 2 5 7

and:

x = 2

the upper bound points to 5.

int pos = upper_bound(a.begin(), a.end(), x) - a.begin();

These two functions are extremely useful in Codeforces problems.

4. The More Powerful Idea: Binary Search on Answer

Now comes the interesting part.

Consider this problem:

You have N machines. Each machine takes some amount of time to produce one item. Find the minimum time required to produce at least K items.

Suppose:

machines = [2, 3, 7]
K = 10

Can we calculate the answer directly?

It may not be obvious.

Instead, let's ask a different question:

If I give the machines X seconds, can they produce at least K items?

This is a yes/no question.

For example:

X = 10

Machine 1 produces:

10 / 2 = 5

Machine 2:

10 / 3 = 3

Machine 3:

10 / 7 = 1

Total:

5 + 3 + 1 = 9

So:

10 seconds → NO

Try:

X = 12

We get:

12/2 + 12/3 + 12/7
= 6 + 4 + 1
= 11

Therefore:

12 seconds → YES

Notice the pattern:

Time increases
      ↓
Production never decreases
      ↓
NO NO NO NO YES YES YES

This monotonic property is exactly what allows Binary Search.

5. Binary Search on a Monotonic Function

The general structure is:

Possible(x) = false

false false false false true true true
                         ↑
                    answer

We want to find the first true.

This is one of the most important Binary Search patterns in competitive programming.

6. Implementation

bool possible(long long time,
              vector<long long>& machines,
              long long k) {

    long long produced = 0;

    for(long long x : machines) {
        produced += time / x;

        if(produced >= k)
            return true;
    }

    return false;
}

Now the Binary Search:

long long l = 0;
long long r = 1e18;

while(l < r) {

    long long mid = l + (r - l) / 2;

    if(possible(mid, machines, k))
        r = mid;
    else
        l = mid + 1;
}

cout << l << '\n';

The important part is that we are not searching for a value inside an array.

We are searching the possible answer space.

7. How to Recognize Binary Search on Answer

Whenever you see a problem asking for:

• Minimum possible value
• Maximum possible value
• Minimum time
• Maximum distance
• Minimum capacity
• Maximum number of elements
• Minimum cost

ask yourself:

Can I check whether an answer X is possible?

If the answer to this question is yes, then ask:

If X is possible, will larger/smaller values also be possible?

If there is a monotonic relationship, Binary Search may be applicable.

8. Another Classic Example: Minimum Maximum Distance

Suppose we have positions:

1 2 4 8 9

We want to place K elements such that the minimum distance between any two selected positions is as large as possible.

Instead of directly finding the maximum distance, suppose we guess:

distance = 4

Now we ask:

Can we place K elements such that every consecutive selected element is at least 4 apart?

If yes:

distance = 4 → possible

Then perhaps we can try a larger distance.

If no:

distance = 4 → impossible

Then we need a smaller distance.

Again, we get:

Possible Possible Possible Impossible Impossible
                    ↑
                 boundary

This is Binary Search on Answer.

9. A Useful Template

For many problems, I use this mental template:

bool check(long long x) {
    // Is x a valid answer?
}

long long lo = minimum_possible;
long long hi = maximum_possible;

while(lo < hi) {

    long long mid = lo + (hi - lo) / 2;

    if(check(mid))
        hi = mid;
    else
        lo = mid + 1;
}

return lo;

The difficult part is usually not writing the Binary Search.

The difficult part is designing:

check(x)

Once the correct monotonic condition is found, the Binary Search itself is usually straightforward.

10. Common Mistakes

Mistake 1: Using Binary Search Without Monotonicity

Binary Search does not magically work on every problem.

There must be some ordered structure or monotonic property.

Mistake 2: Incorrect Search Bounds

Always determine:

minimum possible answer
maximum possible answer

carefully.

Mistake 3: Integer Overflow

Prefer:

long long

when the answer or intermediate calculations can be large.

And calculate middle as:

mid = l + (r - l) / 2;

Mistake 4: Incorrect Boundary

There are several Binary Search variants:

first true
last true
first >= x
last <= x
exact value

Before coding, clearly identify which boundary you need.

11. The Main Pattern to Remember

When you see a problem asking for a minimum or maximum, don't immediately think:

"How do I calculate the answer?"

Instead think:

"If I guess an answer X, can I verify it?"

If you can efficiently verify it and the result is monotonic, Binary Search can often reduce the search from:

O(N)

or even an enormous answer range to:

O(log Answer)

combined with the complexity of the check() function.

Conclusion

Binary Search is much more than searching for an element in a sorted array.

The most useful mindset is:

Find the answer
       ↓
Can I guess an answer X?
       ↓
Can I check X efficiently?
       ↓
Is the check monotonic?
       ↓
Binary Search

Once this pattern becomes familiar, many problems that initially look like greedy, simulation, or brute force problems become much easier to approach.

Don't just memorize Binary Search. Learn to recognize the monotonicity behind it.

Happy Coding!