Sqrt(x)

Problem

Implement int sqrt(int x).

Compute and return the square root of x.

Solution

Regular Binary Search Solution: O(log_2 n) time

public class Solution {
    public int mySqrt(int x) {
        if (x <= 0) return x;
        long start = 0, end = x / 2 + 1;
        while (start <= end) {
            long mid = start + (end - start) / 2;
            if (mid * mid == x) return (int) mid;
            if (mid * mid < x) start = mid + 1; //We set start with mid, hence we need to init start as long
            else end = mid - 1;
        }
        return (int) end;
    }
}

Newton's Method: O(log_2 n) time maybe

public class Solution {
    public int mySqrt(int x) {
        if (x <= 0) return x;
        long res = x; //avoid overflow 
        while (res * res > x) res = (res + x / res) / 2;
        return (int) res;
    }
}

Analysis

In the first solution, we use binary search to get square root
Notice that we must return end to convert decimal to int 2.3 to 2 for example
In the second solution, we use Newton's method
To prove it, we can use formula a + b >= 2 * sqrt(ab)
Therefore, as long as res * res > x, we update res = (res + x / res) / 2
Because of the formula above, res >= 2 * sqrt(res * x / res) / 2 = sqrt(x)
Therefore, the res is the result we need to get