Implement int sqrt(int x).
Compute and return the square root of x.
这是一道数值处理的题目，和Divide Two Integers不同，这道题一般采用数值中经常用的另一种方法：二分法。基本思路是跟二分查找类似，要求是知道结果的范围，取定左界和右界，然后每次砍掉不满足条件的一半，知道左界和右界相遇。算法的时间复杂度是O(logx)，空间复杂度是O(1)。代码如下：
class Solution {
public:int sqrt(int x) {if(x<0)return -1;if(x == 0)return 0;int left = 1;int right = x/2+1;while(left <= right) {int m = (left+right)/2;if(x/m >=m && x/(m+1)<(m+1))return m;if(x/m<m)right = m-1;elseleft = m+1;}return 0;}
}; 比较典型的数值处理的题目还有Divide Two Integers，Pow(x,n)等，其实方法差不多，一般就是用二分法或者以2为基进行位处理的方法。