Sqrt(x)
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator.
- For example, do not use
pow(x, 0.5)in c++ orx ** 0.5in python.
Problem with mid * mid:
If mid is a large integer, directly calculating mid * mid can result in an integer overflow. For instance, if mid is a large value like 46341, calculating mid * mid (which would be 2147488281) could exceed the maximum value for a 32-bit integer (which is 2147483647), causing an overflow.
mid <= x / midis equivalent tomid * mid <= xwithout causing overflow, since division has lower risk of overflow compared to multiplication.If
mid <= x / mid, it meansmid * midis still smaller than or equal tox, so the algorithm tries to explore larger values by updatinglow = mid + 1.If
mid > x / mid, it meansmid * midwould exceedxif we were to calculate it, so the algorithm needs to explore smaller values by updatinghigh = mid - 1.
What does mid * mid <= x mean?
This equation essentially checks whether the square of mid is less than or equal to x. In simpler terms, it answers the question:
Is mid a valid candidate for the integer square root of x?
Here’s the key idea:
- The square root of a number
xis a valuessuch thats * s = x. - Since we’re looking for the integer square root, we’re trying to find the largest integer
midsuch thatmid * midis still less than or equal tox.
In the binary search approach you showed earlier, the algorithm checks different values of mid to see if squaring mid gives a result that is smaller than or equal to x—meaning mid is a potential square root of x.
public int mySqrt(int x) {
if (x == 0 || x == 1) {
return x;
}
int low = 1, high = x, result = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
// To avoid overflow, compare mid with x / mid instead of mid * mid
if (mid <= x / mid) {
result = mid;
low = mid + 1; // Move to the right to find a larger value
} else {
high = mid - 1; // Move to the left to find a smaller value
}
}
return result;
}
