Sqrt(x)

Sqrt(x)

 Implement int sqrt(int x).

Compute and return the square root of x.

-------------------------- thinking -----------------------------------
https://leetcode.com/discuss/24942/a-binary-search-solution
https://leetcode.com/discuss/24965/newtons-iterative-method-in-c

int sqrt(int x) {
    double ans    = x;
    double delta  = 0.0001;
    while (fabs(pow(ans, 2) - x) > delta) {
        ans = (ans + x / ans) / 2;
    }
    return ans;
}

The key point is the average result is calculate by "ans = (ans + x / ans) / 2";

For instance, when calculate sqrt(2) :

   Guess Result        Quotient                             Average Result
          1          2 / 1 = 2                            (2 + 1) / 2 = 1.5
         1.5      2 / 1.5 = 1.3333                (1.3333 + 1.5) / 2 = 1.4167
       1.4167    2 / 1.4167 = 1.4118          (1.4167 + 1.4118) / 2 = 1.4142
        ... ...

-------------------------- codes --------------------------------------
class Solution {
public:
    int sqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int left = 1;
        int right = x;
        while (true) {
            int mid = left + (right - left) / 2;
            if (mid > (x / mid)) {
                right = mid - 1;
            } else {
                //bug here -> x could be 26, which can not find an exact sqrt()
                if ((mid + 1) > (x / (mid + 1))) {
                    return mid;
                } else {
                    left = mid + 1;
                }
            }
        }
    }
};

---------------------------- codes --------------------------------------
class Solution {
public:
int sqrt(int x) {
    double ans    = x;
    double delta  = 0.0001;
    while (fabs(pow(ans, 2) - x) > delta) {
        ans = (ans + x / ans) / 2;
    }
    return ans;
}
};