Sqrt(x) II

Description

Implementdouble sqrt(double x)andx >= 0.

Compute and return the square root of x.

Notice

You do not care about the accuracy of the result, we will help you to output results.

Example

Given n = 2 return 1.41421356

Related problems

Sqrt(x)

Implementation

Link: http://lintcode.com/en/problem/sqrtx-ii/

class Solution {
public:
    /**
     * @param x a double
     * @return the square root of x
     */
    double sqrt(double x) {
        // Write your code here
        double start = 0.0;
        double end = x;
        // Note:
        if(x <= 1.0) {
            end = 1.0;
        }
        double eps = 1e-12;
        while(start + eps < end) {
            double mid = start + (end - start) / 2;
            if(mid * mid == x) {
                return mid;
            } else if(mid * mid > x) {
                end = mid;
            } else {
                start = mid;
            }
        }
        return start;
    }
};