题目描述:
Implement int sqrt(int x).
Compute and return the square root of x.
Have you met this question in a real interview? Yes Examplesqrt(3) = 1
sqrt(4) = 2
sqrt(5) = 2
sqrt(10) = 3
ChallengeO(log(x))
题目思路:一道binary search题,boundary是1~x,然后不断缩小范围,就酱。
Mycode(AC = 11ms):
class Solution { public: /** * @param x: An integer * @return: The sqrt of x */ int sqrt(int x) { // write your code here if (x == 0) return x; long long down = 1, upper = x; // 2, 2 while (down < upper) { long long mid = (down + upper) / 2; // 1 if (mid * mid <= x && (mid + 1) * (mid + 1) > x) { return mid; } else if (mid * mid < x) { down = mid + 1; } else { upper = mid - 1; } } return (int)down; } };