题目：

实现 int sqrt(int x) 函数，计算并返回 x 的平方根。

样例：

样例

思路：

用二分搜索法来找平方根

时间复杂度变为$O(logn)$$

参考答案：

class Solution {public:    /*     * @param x: An integer     * @return: The sqrt of x     */    int sqrt(int x) {        // write your code here                if(x < 1)   return 0;        if(x == 1)   return 1;        int start = 0;        int end = x/2 + 1;                while(start+1 < end){            long mid = start + (end-start)/2;//注意，long           if(mid*mid <= x){                start = mid;            }            else{                end = mid;            }        }        return start;    }};