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
:
- low = 0, high = 10
- mid = 5 → 5 * 5 = 25 → too big → high = 4
- mid = 2 → 2 * 2 = 4 → too small → low = 3, answer = 2
- mid = 3 → 3 * 3 = 9 → still small → low = 4, answer = 3
- 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.
Comments
Loading comments...