题解 | #求平方根#

正式链接

todo 了解牛顿迭代法的原理
甚至还有数论的知识；

//这是二分搜索的样子哈，利用移位，还有long 除法进行避免溢出
 int sqrt(int x) {
    if (x <= 0) {
        return 0;
    }

    int left = 1, right = x;
    while (true) {
        int middle = (left + right) >> 1;
        if (middle <= x / middle && (middle+1) > x / (middle+1)) {
            return (int) middle;
        } else if (middle < x / middle) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }

/*
链接：https://www.nowcoder.com/questionTerminal/09fbfb16140b40499951f55113f2166c
来源：牛客网
*/

class Solution {
public:
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    int sqrt(int x) {
        // write code here
        int i = 1;
        int res = 0;
        while( x >=0){
            x -=i;
            i+=2;//next JiShu
            res++;
        }
        return res - 1;
    }
};