Square Root of a Number: Binary Search for the Integer Square Root

• Integer square root – the largest integer r such that r*r <= x.
• Binary search – since squaring is monotonic on non-negative integers, search the range [0, x] for the upper-bound boundary where the square first exceeds x.
• Overflow guard – multiply in long (or compare via division) to prevent overflow when squaring.
• Complexity – O(log x) time, O(1) space.
• Exactness – binary search gives an exact integer result with no floating-point concerns.

What is the integer square root problem?

Given a non-negative integer x, compute the largest integer r such that r * r <= x. This is the "floor" of the mathematical square root. You must not use any built-in square root function, and the solution should run in O(log x) time.

package com.bank.service;

public class IntegerSquareRoot {
    public static int mySqrt(int x) {
        if (x < 2) return x;
        long low = 1, high = x, answer = 0;

        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (mid * mid <= x) {
                answer = mid;       // valid root, try larger
                low = mid + 1;
            } else {
                high = mid - 1;     // too big, try smaller
            }
        }
        return (int) answer;
    }

    public static void main(String[] args) {
        System.out.println("sqrt(0) = " + mySqrt(0));
        System.out.println("sqrt(1) = " + mySqrt(1));
        System.out.println("sqrt(8) = " + mySqrt(8));
        System.out.println("sqrt(16) = " + mySqrt(16));
        System.out.println("sqrt(2147483647) = " + mySqrt(2147483647));
    }
}

sqrt(0) = 0
sqrt(1) = 1
sqrt(8) = 2
sqrt(16) = 4
sqrt(2147483647) = 46340

Why does binary search work here?

Squaring is a monotonic function on non-negative integers. The candidates split cleanly into two groups: those whose square fits (r*r <= x) and those whose square is too big (r*r > x). Binary search locates the boundary between these two groups.

// For x = 8:
// r=0: 0 <= 8  yes
// r=1: 1 <= 8  yes
// r=2: 4 <= 8  yes   <- answer
// r=3: 9 > 8   no   <- boundary
// Binary search finds r=2 in O(log 8) = 3 steps

Why use long for the multiplication?

When x is a large int, the midpoint squared can exceed Integer.MAX_VALUE, causing overflow. Using long for mid and the multiplication prevents this.

// WRONG: int overflow
int mid = (low + high) / 2;
if (mid * mid <= x) { ... }  // mid=46341, mid*mid=2147488281 overflows int!

// CORRECT: use long
long mid = low + (high - low) / 2;
if (mid * mid <= x) { ... }  // mid * mid stays within long range

What about inputs near Long.MAX_VALUE?

For very large inputs (if the problem uses long instead of int), even long multiplication can overflow. In that case, compare via division: mid <= x / mid, with a guard for mid == 0.

// Division-based comparison (no overflow):
if (mid != 0 && mid <= x / mid) {
    answer = mid;
    low = mid + 1;
} else if (mid == 0) {
    answer = 0;
    low = mid + 1;
} else {
    high = mid - 1;
}

How is this different from Newton's method?

Newton's method converges faster in terms of iterations but involves floating-point arithmetic. Binary search is slower per iteration but exact, with no rounding concerns. For the integer square root definition, binary search is preferred because it directly computes the floor without any floating-point.

| Aspect | Binary Search | Newton's Method |
|---|---|---|
| Time | O(log x) | O(log log x) iterations |
| Precision | Exact integer | Floating-point, then cast |
| Overflow risk | Manageable with long | Floating-point range limits |
| Implementation | Simple | Requires convergence check |

// Newton's method (iterative):
double r = x;
while (r * r > x) {
    r = (r + x / r) / 2;
}
// Risk: floating-point rounding may give wrong floor for large inputs

What are the edge cases?

The inputs x=0 and x=1 return x itself. The loop handles both naturally: for x=0, the condition x < 2 returns immediately. For x=1, low=1, high=1, mid=1, 1*1 <= 1, answer=1.

package com.bank.service;

public class SqrtEdgeCases {
    public static void main(String[] args) {
        System.out.println(IntegerSquareRoot.mySqrt(0));  // 0
        System.out.println(IntegerSquareRoot.mySqrt(1));  // 1
        System.out.println(IntegerSquareRoot.mySqrt(3));  // 1 (floor of 1.73)
        System.out.println(IntegerSquareRoot.mySqrt(4));  // 2 (exact)
    }
}

0
1
1
2

What are common mistakes?

The most common mistake is using int for the multiplication, causing overflow on large inputs.

// WRONG: int * int overflows
int mid = low + (high - low) / 2;
if (mid * mid <= x) { ... }  // overflow for mid > 46340

// CORRECT: cast to long
long mid = low + (high - low) / 2;
if (mid * mid <= (long) x) { ... }  // safe

Another mistake is initializing high to x/2, which misses x=1 (sqrt(1) = 1 > 1/2 = 0). Initializing high to x and handling x < 2 separately is safer.

When should you use this technique?

Use binary search for integer square root whenever you need an exact whole-number result without built-in functions. In banking, this applies to sizing square grids, computing lot sizes, or any scenario where the square root must be a precise integer for procurement.

package com.bank.service;

public class LockerGridSizing {
    public static void main(String[] args) {
        int budget = 150; // maximum number of lockers
        int side = IntegerSquareRoot.mySqrt(budget);
        System.out.println("Grid side for " + budget + " lockers: " + side + "x" + side
            + " = " + (side * side) + " lockers");
    }
}

Grid side for 150 lockers: 12x12 = 144 lockers

What should a senior engineer know?

A senior engineer should explain the overflow guard, the division-based comparison for very large inputs, and why binary search is preferred over Newton's method for integer roots. The exactness guarantee matters when the result feeds a physical count or procurement order.

What are common interview follow-up questions?

• Interviewers commonly ask:
• How do you avoid overflow? (Use long, or compare via division.)
• Why not use Math.sqrt? (Problem constraints prohibit it; also floating-point is not exact.)
• Newton's method? (Faster iterations but introduces floating-point precision issues.)
• Can you compute the cube root similarly? (Yes, same binary search with mid*mid*mid.)