Find Square Root Using Binary Search

Given a non-negative integer x, your task is to find its integer square root. The integer square root of x is the greatest integer r such that r * r ≤ x.

You must solve this problem without using any built-in square root functions. If x is negative, return -1 (square root of negative numbers is not defined in real numbers).

Understanding the Problem

We are given a number x, and we need to compute its integer square root. That means we want the largest integer r such that:

• r * r ≤ x
• and (r + 1) * (r + 1) > x

For example, the square root of 10 is approximately 3.16, but since we want only the integer part, we return 3.

This problem becomes interesting when x is very large, because brute force checking every number up to x would be too slow. That’s where binary search helps — it allows us to quickly narrow down our search.

Step-by-Step Solution with Example

Step 1: Identify base cases

First, we handle easy cases directly. If x is 0 or 1, then the square root is just x itself.

Step 2: Initialize binary search range

We set low = 0 and high = x. These define the search range for our answer. We'll repeatedly guess a number mid between low and high.

Step 3: Apply binary search

At each step, we calculate mid = (low + high) / 2, and check mid * mid:

• If mid * mid == x, then we’ve found the exact square root.
• If mid * mid < x, it means mid might be the answer, but we try to find a larger one: low = mid + 1.
• If mid * mid > x, then mid is too large: high = mid - 1.

We keep track of the last value where mid * mid <= x as our best answer so far.

Step 4: Example – x = 10

Let’s see how this works for x = 10:

1. low = 0, high = 10
2. mid = 5 → 5 * 5 = 25 → too big → high = 4
3. mid = 2 → 2 * 2 = 4 → too small → low = 3, answer = 2
4. mid = 3 → 3 * 3 = 9 → still small → low = 4, answer = 3
5. mid = 4 → 4 * 4 = 16 → too big → high = 3

Loop ends, and the last valid answer is 3.

Edge Cases

• Perfect squares: For inputs like 25 or 100, the binary search will land exactly on the square root.
• Non-perfect squares: For 10 or 99, the result will be the floor of the real square root.
• Large numbers: Binary search handles even huge numbers like 1,000,000 efficiently in ~20 steps.
• 0 or 1: Directly return the same number.
• Negative numbers: There’s no real square root for negative inputs. We return -1 to indicate invalid input.
• Invalid or empty input: If the input is null, undefined, or not a number, return -1.

Finally

This is a classic problem where binary search really shines. Instead of looping through all values up to x, we reduce the problem space by half in each iteration.

By understanding how square roots behave, and tracking midpoints smartly, we get a clean and efficient solution that works even for very large numbers — all in O(log x) time.

1. Set low = 0 and high = x.
2. Initialize ans = -1 to keep track of closest answer.
3. While low ≤ high, do:
4. → Find mid = (low + high) / 2.
5. → If mid * mid == x, return mid.
6. → If mid * mid < x, update ans = mid, and move low = mid + 1.
7. → Else, move high = mid - 1.
8. Return ans.

O(1)

Explanation: No additional space is used; only constant variables are needed.