# Square Root – sqrt(x)

Solution – Binary Search

If you don’t remember Newton’s method, then this problem can be solved using Binary Search.
Note that the goal is not to find the exact square root r but to find the floor(r). So we terminate the loop when narrowing down the range to 1.

Notice that we calculate x/mid rather than mid*mid to avoid data overflow.

```public int sqrt(int x) {
if (x < 2) return x;

int low = 0, high = x;
while (high - low > 1) {
int mid = low + (high - low) / 2;
int div = x / mid;
if (mid == div) return mid;
if (mid < div) low = mid;
else high = mid;
}

return low;
}
```

This algorithm runs in time O(logx).
Solution - Babylonian method

The key idea of Babylonian method is that if root is an underestimate of x, then x/root must be an overestimate and the average of the two may reasonably provide a better approximation.

Babylonian method is derived from Newton's method as shown below.
To find the square root of S, it is equivalent to find an x such that f(x) = x^2 - S = 0. And thus, Newton's method uses f(x) and its derivative to approach a better approximation iteratively.

The process is as follows:
Let r_0 be an initial guess.
r_(i+1) = ( r_i + x / r_i ) / 2 for abs(r_(i+1) - r_i) >= e), where e is desired approximation.
To reduce the converge iterations, we use a rough estimation of 2^(floor(d/2)) as the initial estimate, where d is the number of binary digits of x.

``` public int sqrt(int x) {
// initial guess, x_0 = 2^(D/2)
int root = 1;
for (int digit = 0, origin = x; origin > 1; origin >>= 1, ++digit, root <<= (digit & 1));

// calculate root
double r0 = 0, r1 = 1.0*root;
while (Math.abs(r1 - r0) > 0.01) {
r0 = r1;
r1 = (r0 + x/r0) / 2;
}
return (int)r1;
}
```

If the initial guess can be found in constant time, this algorithm runs in time O(loglogn).