69.Sqrt

难度:Easy

69.Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2
Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

求平方根，可以尝试采用二分法；

class Solution {
int mySqrt(int start,int end, int x)
{
    long int mid=(start+end)/2;
    if(mid*mid <=x && (mid+1)*(mid+1)>x) return mid;
    else if(mid*mid>x ) return mySqrt(start, mid,x);
    else  return mySqrt(mid,end,x);
}
public:
    int mySqrt(int x) {
        if(x==0 || x==1) return x;
        return mySqrt(0,x,x) ;
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了90.73%的用户 内存消耗 :8.2 MB, 在所有 C++ 提交中击败了81.90%的用户