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;
    }
}