博文中会简要介绍Leetcode P0069题目分析及解题思路。
“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.
以下是Java的题解代码实现。
class Solution {
public int mySqrt(int x) {
if (x <= 1)
return x;
int left = 0, right = x;
long mid = 0;
while (left <= right) {
mid = (left+right)/2;
if (mid*mid > x)
right = (int) mid-1;
else if (mid*mid < x)
left = (int) mid+1;
else
return (int) mid;
}
return (mid*mid > x)? (int) mid-1: (int) mid;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int mySqrt(int x) {
if (x <= 1)
return x;
int left = 0, right = x;
long mid = 0;
while (left <= right) {
mid = (left+right)/2;
if (mid*mid > x)
right = mid-1;
else if (mid*mid < x)
left = mid+1;
else
return mid;
}
return (mid*mid > x)? mid-1: mid;
}
};