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
Related Problems Expand
class Solution {
public:
/**
* @param x: An integer
* @return: The sqrt of x
*/
int sqrt(int x) {
// write your code here
if (x < 1) {
return 0;
}
long lo = 1;
long hi = x / 2 + 1;
while (lo < hi) {
long mid = (lo + hi) / 2;
long prod = mid * mid;
if (prod <= x) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo - 1;
}
};
还是依照upper_bound的思路