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%的用户