Binary Search on the Answer

Normally you binary search to find a number inside a sorted array. But here is a problem. What if the thing you are looking for is not in any array at all? Say someone asks you for the integer square root of 50. There is no array of answers sitting in memory. The answer is just some number between 1 and 50. So how do you find it fast?

This is where a neat trick comes in. You can binary search over the range of possible answers itself. That is the whole idea of this tutorial.

🎯 The Problem First

Let me give you the pain before the cure.

You want the integer square root of 50. That means the largest whole number whose square is not more than 50. You could start at 1 and try every number. 1, 2, 3, 4, 5, 6, 7. At 7 the square is 49 which is fine. At 8 the square is 64 which is too big. So the answer is 7.

That works. But what if the number is huge, like 10 billion? Trying one by one is painfully slow. You would do billions of checks.

The fix is binary search on the answer. Instead of walking through every candidate, you cut the range of possible answers in half each time. So even a huge range gets solved in very few steps.

🌍 A Real-World Analogy

Think of a guessing game. Riya picks a secret number between 1 and 100. You guess. After each guess she only tells you “too high” or “too low”.

What do you do? You don’t guess 1, 2, 3 one by one. You guess 50 first. If she says too low, the answer is somewhere in 51 to 100. So you throw away the bottom half. Then you guess 75. And so on. Each guess cuts the leftover range in half.

Binary search on the answer is exactly this game. The secret number is your answer. The “too high” or “too low” hint comes from a small check you write yourself.

📚 What Is Binary Search on the Answer?

Here is the plain meaning.

You are not searching inside an array. You are searching inside a range of numbers where the answer could live. You keep a low and a high. You pick the middle value. You ask one yes-or-no question about it. Then you throw away the half that cannot hold the answer.

The yes-or-no question has a name. We call it the feasibility check. It is a small function. It takes a candidate value and answers one thing. “Is this value good enough?” Yes or no. Nothing more.

For the square root problem the feasibility check is easy. Given a candidate x, ask: is x times x not more than n? If yes, then x could be the answer, or the answer is even bigger. If no, then x is too big and the real answer is smaller.

🔑 The One Rule That Makes It Work

This trick does not work on every problem. There is one thing the problem must have. We call it being monotonic. That just means the Yes answers and No answers do not mix together. They stay in two clean blocks.

Picture the candidates lined up from small to big. The feasibility check should look like this.

candidate:  1   2   3   4   5   6   7   8   9   10
good?       Y   Y   Y   Y   Y   Y   Y   N   N   N
                                        ^
                                   the boundary

See how all the Yes values sit together? Then all the No values sit together. There is one clean line where Yes turns into No. That line is your answer. Binary search is great at finding that exact line fast.

If your problem looks like Y N Y N Y mixed up randomly, then binary search on the answer will not work. So before you use this pattern, always check one thing. Do the good answers form one solid block?

⚙️ How It Works Step by Step

Let me walk through finding the integer square root of 50.

• Start with low = 0 and high = 50. The answer is somewhere in here.
• Pick the middle. mid = 25. Check: is 25 * 25 = 625 not more than 50? No, way too big. So the answer is smaller. Move high down to 24.
• New range 0 to 24. mid = 12. Is 12 * 12 = 144 not more than 50? No. Move high to 11.
• New range 0 to 11. mid = 5. Is 5 * 5 = 25 not more than 50? Yes. So 5 works. But maybe a bigger number also works. Save 5 as a possible answer and move low up to 6.
• New range 6 to 11. mid = 8. Is 8 * 8 = 64 not more than 50? No. Move high to 7.
• New range 6 to 7. mid = 6. Is 6 * 6 = 36 not more than 50? Yes. Save 6. Move low to 7.
• New range 7 to 7. mid = 7. Is 7 * 7 = 49 not more than 50? Yes. Save 7. Move low to 8.
• Now low = 8 is greater than high = 7. Stop. The last saved answer is 7.

We found it in seven checks. The walk-through earlier also needed seven steps. So on this small number the win looks tiny. But for a billion-sized range the walk-through would take a billion steps. This takes only about thirty. That is the power of cutting in half.

🧮 Visualizing the Search

Here is the shape of how the range shrinks each round.

Each box is one round. The range gets smaller every time until low passes high.

💻 Code: Integer Square Root

Now let me show the actual code in all five languages. The idea is the same everywhere. We keep a low and high. We find the middle safely. We run the feasibility check mid * mid <= n. Then we slide the boundary.

One small but important detail. To find the middle we write low + (high - low) / 2 instead of (low + high) / 2. Why? Because if low and high are both very large, then adding them can overflow and break. The first form avoids that.

#include <stdio.h>

// Feasibility check: is mid*mid not more than n?
// We use long long so mid*mid does not overflow.
int feasible(long long mid, long long n) {
    return mid * mid <= n;
}

// Binary search on the answer: find the integer square root of n.
long long integer_sqrt(long long n) {
    long long low = 0, high = n, answer = 0;
    while (low <= high) {
        long long mid = low + (high - low) / 2; // safe middle
        if (feasible(mid, n)) {
            answer = mid;   // mid works, remember it
            low = mid + 1;  // try to go higher
        } else {
            high = mid - 1; // mid too big, go lower
        }
    }
    return answer;
}

int main(void) {
    printf("Integer square root of 50 is %lld\n", integer_sqrt(50));
    printf("Integer square root of 100 is %lld\n", integer_sqrt(100));
    return 0;
}

Integer square root of 50 is 7
Integer square root of 100 is 10

#include <iostream>
using namespace std;

// Feasibility check: is mid*mid not more than n?
bool feasible(long long mid, long long n) {
    return mid * mid <= n;
}

// Binary search on the answer: find the integer square root of n.
long long integerSqrt(long long n) {
    long long low = 0, high = n, answer = 0;
    while (low <= high) {
        long long mid = low + (high - low) / 2; // safe middle
        if (feasible(mid, n)) {
            answer = mid;   // mid works, remember it
            low = mid + 1;  // try to go higher
        } else {
            high = mid - 1; // mid too big, go lower
        }
    }
    return answer;
}

int main() {
    cout << "Integer square root of 50 is " << integerSqrt(50) << endl;
    cout << "Integer square root of 100 is " << integerSqrt(100) << endl;
    return 0;
}

Integer square root of 50 is 7
Integer square root of 100 is 10

public class IntegerSqrt {

    // Feasibility check: is mid*mid not more than n?
    static boolean feasible(long mid, long n) {
        return mid * mid <= n;
    }

    // Binary search on the answer: find the integer square root of n.
    static long integerSqrt(long n) {
        long low = 0, high = n, answer = 0;
        while (low <= high) {
            long mid = low + (high - low) / 2; // safe middle
            if (feasible(mid, n)) {
                answer = mid;   // mid works, remember it
                low = mid + 1;  // try to go higher
            } else {
                high = mid - 1; // mid too big, go lower
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println("Integer square root of 50 is " + integerSqrt(50));
        System.out.println("Integer square root of 100 is " + integerSqrt(100));
    }
}

Integer square root of 50 is 7
Integer square root of 100 is 10

# Feasibility check: is mid*mid not more than n?
def feasible(mid, n):
    return mid * mid <= n

# Binary search on the answer: find the integer square root of n.
def integer_sqrt(n):
    low, high, answer = 0, n, 0
    while low <= high:
        mid = low + (high - low) // 2  # safe middle
        if feasible(mid, n):
            answer = mid    # mid works, remember it
            low = mid + 1   # try to go higher
        else:
            high = mid - 1  # mid too big, go lower
    return answer

print("Integer square root of 50 is", integer_sqrt(50))
print("Integer square root of 100 is", integer_sqrt(100))

Integer square root of 50 is 7
Integer square root of 100 is 10

// Feasibility check: is mid*mid not more than n?
function feasible(mid, n) {
  return mid * mid <= n;
}

// Binary search on the answer: find the integer square root of n.
function integerSqrt(n) {
  let low = 0, high = n, answer = 0;
  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2); // safe middle
    if (feasible(mid, n)) {
      answer = mid;    // mid works, remember it
      low = mid + 1;   // try to go higher
    } else {
      high = mid - 1;  // mid too big, go lower
    }
  }
  return answer;
}

console.log("Integer square root of 50 is", integerSqrt(50));
console.log("Integer square root of 100 is", integerSqrt(100));

Integer square root of 50 is 7
Integer square root of 100 is 10

🚚 Another Example: Minimum Speed

The square root case is nice for learning. But the real strength shows up in word problems. Let me give you one.

Arjun has to deliver a list of packages. Each package takes a number of hours that depends on the truck’s speed. He has a deadline of H hours total. Question: what is the slowest speed that still finishes all deliveries within H hours?

Why the slowest speed? Because a slower truck is cheaper. So Arjun wants the smallest speed that still makes the deadline.

This is binary search on the answer again. Watch how it maps.

• The answer is a speed. It lives in a range, say from 1 up to the largest package size.
• The feasibility check takes a speed and asks one thing. “At this speed, do all packages finish within H hours?” Yes or no.
• It is monotonic. A faster speed always finishes in equal or less time. So once a speed is fast enough, every faster speed is also fine. All the Yes answers sit together. Perfect.

So we binary search the speed range. If a speed is fast enough, that is a Yes. We save it and try a slower one. If it is too slow, that is a No. We go faster. The smallest Yes is the answer.

⏱️ How Fast Is It?

Speed is the whole reason we do this. Let me put the numbers in a table.

Say the answer can be anywhere in a range of size R. And one feasibility check costs C work.

The range R goes from billions down to about thirty checks. That is because log of a billion is roughly thirty. For the plain square root the feasibility check is just one multiplication. So the whole thing is O(log R).

⚠️ Common Mistakes

A few traps catch beginners. Watch out for these.

• Using this pattern when the problem is not monotonic. If the Yes and No answers are mixed up, the search lands on the wrong spot. Always confirm the good answers form one solid block first.
• Writing (low + high) / 2 for the middle. With very large numbers this can overflow. Use low + (high - low) / 2 instead.
• Sliding the boundary the wrong way. On a Yes, decide clearly whether you want bigger or smaller. Then move the matching side. Getting this backwards gives the opposite answer.
• Forgetting to save the answer. The loop ends when low passes high. So you must store the last good value during the loop, not after.
• Mixing up “minimum that works” and “maximum that works”. They need the boundary handled in opposite directions. Decide which one the question wants before you code.

🧩 What You’ve Learned

✅ Binary search on the answer searches a range of possible answers, not an array.

✅ The feasibility check is a small yes-or-no function that asks “is this value good enough?”

✅ The pattern only works when the problem is monotonic. That means all the Yes answers sit in one solid block, right next to all the No answers.

✅ On a Yes, save the value. Then slide toward the side you want. On a No, slide the other way.

✅ It turns a slow O(R) walk-through into a fast O(log R) search. So a billion-sized range needs only about thirty checks.

✅ Use the safe middle low + (high - low) / 2 to avoid overflow with large numbers.

🚀 What’s Next?

• Binary Search
• Lower Bound and Upper Bound