04-x的平方根

问题描述

在不使用sqrt(x)方法下，求x的平方根的整数部分。

问题解决

暴力解决：

public static int test1(int n) {  
    for (int i = 0; i < n; i++) {  
        if(i*i == n){  
            return i;  
        }else if (i*i < n){  
           if((i+1)*(i+1) > n){  
               return i;  
           }  
        }  
    }  
    return -1;  
}

二分方式解决：

public static int test(int n) {  
    int l = 0;  
    int r = n; // 根号n  < n  
    int index = -1; //  
    while(l <= r){  
        int mid = l + (r-l)/2; 
        // < 是整数部分 = 刚好是 
        if(mid * mid <= n){    
             index = mid;  
             l = l + 1;  
        }else if(mid * mid > n) {  
            // 在左边  
            r = r - 1;  
        }  
    }  
    return index;  
}

牛顿迭代

1,2,3
(n+1)*n/2