Easy
Binary Search O(logN), 总结点小经验，碰到会一直求平方的情况，一开始用long定义变量可以防止中间溢出.
class Solution {
public int mySqrt(int x) {
if (x == 0){
return 0;
}
//8
//start 2
//end 3
//mid 3
//square 9
long start = 1;
long end = x;
long mid = 0;
while (start + 1 < end){
mid = start + (end - start) / 2;
long square = mid*mid;
if (square == x){
return (int) mid;
} else if (square > x){
end = mid;
} else {
start = mid;
}
}
return (int) start;
}
}
Naive时间复杂度O(N)
class Solution {
public int mySqrt(int x) {
if (x == 0){
return 0;
}
long i = 1;
while (i*i <= x){
if (i*i == x){
return (int) i;
}
i++;
}
return (int)(i - 1);
}
}
