Finding Square Root of a Number using Binary Search (BS-10)

Finding the square root of an integer (or specifically, its floor value) is the foundational introduction to the powerful algorithmic pattern known as Binary Search on Answers. This chapter explores how to transition from an inefficient linear search approach to an optimal logarithmic search by recognizing monotonic properties in solution spaces.

1. Problem Statement & Overview

When given an integer $n$, the goal is to find the floor of its square root.

• If $n = 25$, the exact square root is $5$, so we return $5$.
• If $n = 28$, the square root is $5.2915...$, so we return the floor integer value: $5$.
• If $n = 36$, the exact square root is $6$, so we return $6$.

Formally, we are searching for the maximum integer $x$ such that:

2. The Naive Approach: Linear Search

The most intuitive approach is to check every possible integer starting from $1$ upwards until the square exceeds $n$.

Linear Search Code Walkthrough

long long answer = 1;
for (long long i = 1; i <= n; i++) {
    if (i * i <= n) {
        answer = i;
    } else {
        break; // i * i has exceeded n, further values will also exceed n
    }
}

Limitations of Linear Search

• Time Complexity: $\mathcal{O}(\sqrt{n})$ in the worst case (or $\mathcal{O}(n)$ depending on how the loop bounds are defined).
• Inefficiency: As $n$ grows large (e.g., $10^9$), linear traversal takes too many operations, making it unacceptable for competitive programming and large-scale systems.

3. The Core Mental Model: Monotonicity

To apply Binary Search, we must recognize a fundamental pattern in the answer space: monotonicity (sorted behavior).

Let us take $n = 28$ and evaluate integers from $1$ to $28$:

Integer:  1   2   3   4   5   6   7   8   ...   28
i * i:    1   4   9  16  25  36  49  64         (exceeds 28)
Status:  [OK][OK][OK][OK][OK][ X ][ X ][ X ]  ...  [ X ]
                             ^
                             |
                     Threshold point

Observe the pattern:

1. Valid Zone (Possible Answers): For numbers $1, 2, 3, 4, 5$, their squares are $\le 28$. These are valid candidate answers.
2. Invalid Zone (Impossible Answers): For numbers $6, 7, 8, \dots, 28$, their squares exceed $28$. Crucially, once a number's square exceeds $n$, all subsequent larger numbers will also exceed $n$.

Because the search space is partitioned neatly into a [Valid Zone] followed by an [Invalid Zone], we can use Binary Search to find the boundary.

4. Step-by-Step Dry Run ($n = 28$)

Let's trace the binary search boundaries:

• Initial Setup: low = 1, high = 28, answer = 1

Iteration 1

• mid = (low + high) / 2 = (1 + 28) / 2 = 14
• Check condition: 14 * 14 = 196 ($\le 28$? False).
• Inference: $14$ is too large. Everything from $14$ to $28$ is invalid. Eliminate the right half.
• Update: high = mid - 1 = 13

Iteration 2

• low = 1, high = 13
• mid = (1 + 13) / 2 = 7
• Check condition: 7 * 7 = 49 ($\le 28$? False).
• Inference: $7$ is too large. Eliminate the right half (8 to 13).
• Update: high = mid - 1 = 6

Iteration 3

• low = 1, high = 6
• mid = (1 + 6) / 2 = 3
• Check condition: 3 * 3 = 9 ($\le 28$? True).
• Inference: $3$ is a valid candidate! Store answer = 3. But there might be a larger valid number on the right. Search right.
• Update: low = mid + 1 = 4

Iteration 4

• low = 4, high = 6
• mid = (4 + 6) / 2 = 5
• Check condition: 5 * 5 = 25 ($\le 28$? True).
• Inference: $5$ is valid! Store answer = 5. Search right for a potential larger match.
• Update: low = mid + 1 = 6

Iteration 5

• low = 6, high = 6
• mid = (6 + 6) / 2 = 6
• Check condition: 6 * 6 = 36 ($\le 28$? False).
• Inference: $6$ is invalid. Eliminate right half.
• Update: high = mid - 1 = 5

Termination: Loop ends because low (6) > high (5). The final answer stored is $5$.

5. Comparative Strategy: Linear vs. Binary Search

6. Production-Ready Code (C++)

Here is the robust, optimal implementation handling potential integer overflows using long long.

#include <iostream>

using namespace std;

long long floorSqrt(long long n) {
    long long low = 1, high = n;
    long long ans = 1;

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        
        // Check if mid * mid <= n
        if (mid * mid <= n) {
            ans = mid;         // Save as a potential answer
            low = mid + 1;     // Look for a larger valid integer on the right
        } else {
            high = mid - 1;    // Too large, eliminate right half
        }
    }
    return ans; // Alternatively, returning 'high' also yields the correct answer
}

int main() {
    long long n = 28;
    cout << "Floor of Square Root of " << n << " is: " << floorSqrt(n) << endl;
    return 0;
}

7. Real-World Debugging & Integer Overflow Pitfalls

Note: When working with large numbers in systems programming or competitive coding, always anticipate boundary overflows.

• The Overflow Trap: If $n = 10^9$, computing mid * mid where mid approaches $10^9$ results in $10^{18}$, which easily overflows a standard 32-bit signed integer (int max limit is $\approx 2 \times 10^9$).
• The Fix: Always use long long data types for low, high, mid, and multiplication checks to prevent silent arithmetic overflows and incorrect calculation results.
• Alternative Return Value: Notice that when the binary search terminates (low > high), the high pointer always lands precisely on the floor square root value. You can return either ans or high.

8. Summary and Key Takeaways

• Binary Search on Answers Pattern: Applicable whenever you are searching for a minimum or maximum value within a known numerical range where a condition cleanly splits the domain into valid and invalid zones.
• Answer Range: For finding the square root of $n$, the possible answer range is bounded between 1 and n.
• Monotonic Condition: If mid * mid <= n, store mid as a candidate and search the right half (low = mid + 1) to find a greater valid integer.
• Elimination Strategy: If mid * mid > n, the value is too large, so eliminate the entire right half by moving high = mid - 1.
• Logarithmic Efficiency: Reduces time complexity from $\mathcal{O}(\sqrt{n})$ down to $\mathcal{O}(\log n)$.
• Overflow Prevention: Always utilize long long types when multiplying midpoints to guard against constraints up to $10^9$ and beyond.