title: sqrtx
tags:
- sqrtx
- No.69
- simple
- binary-search
- mathematical-analysis
- overflow
Problem
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
Corner Cases
- Integer overflow
sqrt(x) >= sqrt(2147483647) = 51453 - zero
Solutions
Binary Search
For function \sqrt{x}, its derivative is:
\frac{d}{dx} \sqrt{x} = \frac{1}{2 \sqrt{x}}
thus, for line:
y = \frac{1}{2 \sqrt{x_0}} (x - x_0) + \sqrt{x_0}
we have inequalities:
\frac{1}{2 y_0} (x - y_0^2) + y_0 \geq \sqrt{x}, x \geq x_0
For y_0 = 1, we can narrow the range to the half before binary search.
Note that the limits of int type, for a > 2^{16}, we cannot compare a^2 since it is greater than 2^{32}.
long type can solve this problem. Since for int, a < 2^{32}, then a^2 < 2^{64}. Another way is to turn int to uint. Though java do not have unsigned type, there exists a method to compare them.
Running time is O(lg(x)).
class Solution {
public int mySqrt(int x) {
if (x == 0) {return 0;}
long i = 1;
long j = x / 2 + 1;
long m;
while (i != j && i+1 != j) {
m = (i + j) / 2;
i = (x < m*m) ? i : m;
j = (x < m*m) ? m : j;
}
return (int)i;
}
}
