leetcode 69. x 的平方根
2020-10-26 本文已影响0人
Source_Chang
二分查找：
C++：
class Solution {
public:
int mySqrt(int x) {
if ( x == 1 ) {
return x;
}
int left = 0;
int right = x;
int middle = left + (right - left) / 2;
while ( left < right ) {
middle = left + (right - left) / 2;
long long multiply = (long long)middle * middle;
if ( middle == left || multiply == x ) {
break;
}
if ( multiply < x ) {
left = middle;
} else {
// multiply > x
right = middle;
}
}
return middle;
}
};
