描述#
實現 int sqrt(int x) 函數。
計算並返回 x 的平方根，其中 x 是非負整數。
由於返回類型是整數，結果只保留整數的部分，小數部分將被捨去。
示例 1:
輸入: 4
輸出: 2
示例 2:
輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842...,
由於返回類型是整數，小數部分將被捨去。
思路#
- 暴力無腦解法，從 1 開始自增求平方，結果大於 x 則輸出該值減一
int mySqrt(int x){
for(long i=1;;i++) {
if(i*i > x)
return (int)i-1;
}
}
思路二#
- 在之前的基礎上，把自增的跨度增大，查找寬範圍，再递减查找最終值
int mySqrt(int x){
long first = 1;
for(;first < x;first *= 2)
if(first * first >= x)
break;
for(long second = first;;second--)
if(second * second <= x)
return second;
}