sqrt(int x)

Implement int sqrt(int x).
Compute and return the square root of x.

http://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots


1. Newton method

class Solution {
public:
    int sqrt(int x) {
        double a = double(x);
        double r=1;
        double res;
       
        while(1)
        {
            res=0.5*(r+a/r);
            if (abs(res-r)<1e-10)
               break;
            r=res;
        }
       
        return int(res);
    }
};

2. Binary search: The int is rounded to lower.
a. Remember to use division instead of multiplication.
b. low+1<hi
c. hi=mid; low=mid

class Solution {
public:
    int sqrt(int x) {
        if (x<=1) return x;
       
        int mid =1, low=1, hi=x;
       
        while (low+1<hi)
        {
            mid=low+(hi-low)/2;
            if (mid==x/mid)
               return mid;
            else if (mid>x/mid)
            {
                hi=mid;
               
            }
            else
            {
                low=mid;
            }
        }
        return low;
    }
};