To find the integer square root of a number x
, we aim to identify the largest number whose square is less than or equal to x
. Instead of testing each number from 1 up to x
, which would be slow for large values, we use binary search for efficiency.
Understanding the Problem
The square root of a number x
is a number r
such that r * r ≤ x
and (r + 1) * (r + 1) > x
. We want this integer value of r
.
Different Input Scenarios
- Case 1 – Perfect Square: If
x
is a perfect square like 25 or 100, then the square root is exact. For example, 5 * 5 = 25, so the answer is 5.
- Case 2 – Not a Perfect Square: For values like 10 or 99, the square root won’t be exact. We return the floor of the real square root. For 10, the real root is ~3.16, but we return 3.
- Case 3 – Very Large Input: The binary search method still works efficiently even for inputs like 1,000,000. The loop only runs about log₂(x) times.
- Case 4 – Small Numbers (0 or 1): These are trivial cases. The square root of 0 is 0, and the square root of 1 is 1.
- Case 5 – Negative Numbers: Since we’re dealing with real numbers only, there’s no square root defined for negatives. We return -1 for input like -25.
- Case 6 – Empty or Invalid Input: If the input is empty or not a number, we treat it as invalid and return -1 to indicate the error.
How Binary Search Helps
We use binary search to guess a number mid
between 0 and x
and check if mid * mid
is equal to, less than, or greater than x
. Based on that, we move the low
and high
pointers and gradually narrow down the search range. We also store the last value of mid
that gives mid * mid ≤ x
— this becomes our final answer.
This approach is very efficient and gives us the result in O(log x) time without needing any built-in math functions.