Question from lintcode

Implement double sqrt(double x) and x >= 0.

Compute and return the square root of x.

Example
Given n = 2 return 1.41421356

Idea

Almost the same as yesterday. BUT, this one asks for a double type result. So the trick is you shrink the answer to a small enough err zone with binary search, by which time you can return either left or right.

public class Solution {
    /*
     * @param x: a double
     * @return: the square root of x
     */
    public double sqrt(double x) {
        double left = 0.0;
        double right = x;
        double err = 1e-12;
        
        if (right < 1.0) {
            right = 1.0;
        }
        
        while (right - left > err) {
            double mid = (right + left) /2;
            if (mid * mid < x) {
                left = mid;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
}