LeetCode - Sqrt(x) | Darren's Blog

Implement int sqrt(int x). Compute and return the square root of x.
we can make this search process faster by dividing the range into two halves and deciding whether the square root is found and which half to explore according to the center value of the range. The idea of this accelerated process is similar to binary search of a target value in a sorted array. Note that when coding the above process, do avoid integer overflowing.

public int sqrt(int x) {

        if (x < 0)

            return -1;

        if (x == 0)

            return 0;

        int lower = 1, upper = x/2+1;   // Lower and upper bound of sqrt(x)

        while (lower <= upper) {

            int center = (lower+upper) / 2;

            if (center <= x/center && center+1 > x/(center+1))  // Use this form to avoid overflow

                return center;

            if (center < x/center)  // sqrt(x) is in the right half

                lower = center + 1;

            else        // sqrt(x) is in the left half

                upper = center - 1;

        }

        // Dummy return

        return 0;

    }

According to Newton's Method(http://en.wikipedia.org/wiki/Newton's_method), we can use

to get the sqrt(x)

int sqrt(int x) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        if (x==0) {return 0;}

        if (x==1) {return 1;}

       

        double x0 = 1;

        double x1;

        while (true){

            x1 = (x0+ x/x0)/2;

            if (abs(x1-x0)<1){return x1;}

            x0=x1;

        }

         int sqrt(int x) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        if (x==0) {return 0;}

        if (x==1) {return 1;}

       

        double x0 = 1;

        double x1;

        while (true){

            x1 = (x0+ x/x0)/2;

            if (abs(x1-x0)<1){return x1;}

            x0=x1;

        }

Read full article from LeetCode - Sqrt(x) | Darren's Blog