141. Sqrt(x)

题目

实现 int sqrt(int x) 函数,计算并返回 x 的平方根。http://www.lintcode.com/zh-cn/problem/sqrtx/

样例
sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

分析

题目中要求的平方根是整数,其实应该这样表述,对于给定的整数n,找到一个整数x,使得x*x <= n 且 (x+1)*(x+1) > n

求平方根有一个很经典的牛顿迭代开方法,相关的代码网上有很多,不再赘述。这道题目其实还可以通过二分查找法求解。回忆一下 y = x1/2的曲线和y = 1/2 * x的曲线,如下图
函数图

这两条函数在(0, + ∞)存在一个交点(4,2),当x不超过4时,显然开方的结果大于y=1/2*x;而之后,平方根必然小于1/2*x。小于等于4的情况可以枚举结果,就不讨论了。超过4时,显然,最终平方根的结果必然介于[5, 1/2*x -1]之间。接着,就是在这个区间里进行二分查找。就可以快速求出符合要求的结果。

代码


public class Solution {

 
    public long findSqrt(long min, long max, long target){
        long mid = (min + max)>>1;
        
        long r = mid * mid;
        long r1 = r+ 2*mid +1;
        
        if( r <= target && r1 > target){
            return mid;
        }
        
        if( r1 < target){
            return findSqrt(mid, max, target);
        }
        
        if( r > target){
            return findSqrt(min, mid, target);
        }
        
        return -1;
    }
   
    public int sqrt(long x) {
        if(x <= 0) return 0;
        if( x == 1) return 1;
        if(x <=4 ) return (int)x<<1;
        
        return (int)findSqrt(5l, x/2-1, x);

    }
}

Show Comments

Get the latest posts delivered right to your inbox.