【leetcode】sqrt

问题：

Implement int sqrt(int x).

Compute and return the square root of x.

分析：

1、二分法。

代码：

class solution{ public: int sqrt(int x){ if(x<2) return x; int left=1,right=x/2; int last_mid; //二分法求sqrt while(left<=right){ int mid=left+(right-left)/2; //不能写成x>mid*mid，否则会溢出； if(x/mid>mid){ left=mid+1; last_mid=mid; }else if(x/mid<mid){ right=mid-1; }else{ return mid; } } return last_mid; } };