Implement int sqrt(int x).
Compute and return the square root of x.
题目大意：实现求一个int的根。
解题思路：二分。
public class Solution {
public int mySqrt(int x) {
if (x <= 0) {
return 0;
}
if (x <= 3) {
return 1;
}
long num = x / 2;
int tmp = x;
while (num * num >= tmp) {
if (x / 2 == 0) {
break;
}
num = x / 2;
x /= 2;
}
long low = num, high = num * 2, mid = 0;
while (low <= high) {
mid = (low + high) >> 1;
if (mid * mid <= tmp && (mid + 1) * (mid + 1) > tmp) {
break;
} else if (mid * mid > tmp) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return (int) mid;
}
}