题解 | #求平方根#

根据题目要求时间复杂度O(logn)可以知道使用二分法，然后递归是最容易想到的，每次对x都除2，然后根据中点和x的大小关系来判断该往中点下方继续除还是从中点上方除，直到：

• 中点的平方与x相等
• 中点的平方小于x但中点加一的值的平方大于x

既此中点就是x的平方根。

需要注意的是中点的平方很大，需要用long int型存，当然在递归函数里需要一个static型的变量来存结果。

代码如下：

public:
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    int sqrt(int x) {
        // write code here
        return getSqrt(1, x, x);
    }
    int getSqrt(int start, int end, int x){
        long int mid = (start+end)/2;
        long int num = mid*mid;
        static long int res = 1;
        if(num == x || (num<x && (mid+1)*(mid+1)>x)){
            res = mid;
        }else if(num < x){
            getSqrt(mid+1, end, x);
        }else if(num > x){
            getSqrt(start, mid, x);
        }
        return res;
    }
};