Lintcode: Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Have you met this question in a real interview? 

Yes

Example

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

Challenge

O(log(x))

Tags Expand 

Binary Search Mathematics

Way 1: Binary search:
Remember the format: like start <= end, return start - 1
Try input 8 to evaluate why <= is necessary. Because middle = (start + end) / 2 may lost values from end. Equation could make it up.

class Solution {
public:
    /**
     * @param x: An integer
     * @return: The sqrt of x
     */
    int sqrt(int x) {
        long int start = 1;
        long int end = x/2 + 1;
        while(start <= end){
            long int middle = (start + end) / 2;
            if(middle * middle > x) end = middle - 1;
            if(middle * middle <= x) start = middle + 1;
        }
        return start - 1;
    }
};

Way 2: Newton's method
http://www.cnblogs.com/AnnieKim/archive/2013/04/18/3028607.html
Just mathematical solution. Have no interest...



Lintcode second:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: /** * @param x: An integer * @return: The sqrt of x */ int sqrt(int x) { // write your code here long int start = 1; long int end = x / 2 + 1; while(start <= end){ long int mid = (start + end) / 2; if(mid * mid > x) end = mid - 1; else start = mid + 1; } //start points to the first element that more than x //end points to the first element that less or equal than x from right side return end; } };