題目：

69. x 的平方根

難度簡單1280收藏分享切換為英文接收動態(tài)反饋

給你一個非負整數(shù)?x?，計算并返回?x?的?算術(shù)平方根?。

由于返回類型是整數(shù)，結(jié)果只保留?整數(shù)部分?，小數(shù)部分將被?舍去 。

注意：不允許使用任何內(nèi)置指數(shù)函數(shù)和算符，例如?pow(x, 0.5)?或者?x ** 0.5?。

?

示例 1：

輸入：x = 4輸出：2

示例 2：

輸入：x = 8輸出：2解釋：8 的算術(shù)平方根是 2.82842..., 由于返回類型是整數(shù)，小數(shù)部分將被舍去。

?

提示：

• 0 <= x <= 231?- 1

第一種錯法：

class?Solution?{

public:

????int?mySqrt(int?x)?{

? ? ? ?int right,left,mid;

????????right?=?x,left?= 1;

????????while(right>left){

????????????mid?=?(right+left)/2;

????????????if(mid*mid<x){

????????????????left?=?mid+1;

????????????}else?if(mid*mid>x){

????????????????right?=?mid-1;?

????????????}else{

????????? ? ????return mid;

????????????}

????????}

????????return?right-1;

????}

};

現(xiàn)在還是不理解什么時候二分要取等于什么時候不用取等于，還有就是邊界問題

第一種對法：

class?Solution?{

public:

????int?mySqrt(int?x)?{

????????long?long?right,left,mid,ans;

????????right?=?x,left?=?0;

????????while(right>=left){

????????????mid?=?(right+left)/2;

????????????if(mid*mid<=x){

????????????????ans?=?mid;

????????????????left?=?mid+1;

????????????}else?if(mid*mid>x){

????????????????right?=?mid-1;?

????????????}

????????}

????????return?ans;

????}

};