class Solution {
public:
    int sqrt(int x) {
        int r = x;
        while(r*r > x)
        	r = (r + x/r)>>1;
        return r;
    }
};

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        // write code here
        //return (int) Math.sqrt(x);
        for(int i = 0; i <= x; i++){
            if(i * i > x){
                return i - 1;
            }
            if(i * i == x){
                return i;
            }
        }
        return 0;
    }
}

class Solution:
    def sqrt(self , x ):
        # write code here
        if x==0:
            return 0
        if x==1:
            return 1
        if x ==2:
            return 1
        else:
            lower = 0
            ans = 0
            upper = x
            while True:
                mid = (upper - lower) // 2 + lower
                if mid * mid <= x:
                    if (mid + 1) * (mid + 1) > x:
                        ans = mid
                        return ans
                    else:
                        lower = mid
                else:
                    upper = mid

关键注意溢出
int sqrt(int x) {      
        int l=0,r=x;long long mid;
        while(l<=r){
            mid=(l+r)/2;
            if(mid*mid==x) return mid;
            else if(mid*mid<x) l=mid+1;
            else r=mid-1;
        }
        
        if(mid*mid>x) mid--;
        return mid;
    }
};

牛顿迭代法

class Solution:
def sqrt(self , x ):
# write code here
if x==0:
return 0
C,x0=x,x
while True :
xi=0.5*(x0+C/x0)
if abs(x0-xi)<1e-7 :
break
x0=xi
return int(x0)

可采用二分法，但是需要注意溢出问题。

class Solution {
public:
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    int sqrt(int x) {
        int l = 0, r = x;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            long long tmp = 1LL * mid * mid;  // 注意溢出，因此采用 long long
            if (tmp < x) {
                if ((mid + 1) * (mid + 1) > x) {
                    return mid;
                }
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
};

class Solution {
public:
    int sqrt(int x) {
        return pow(x,0.5);
    }
};

Java解法

解法一：可以直接使用库……

public class Solution {
    public int sqrt(int x) {
        return (int) Math.sqrt(x);
    }
}

解法二：根据平方数的性质——连续n个奇数相加的结果一定是平方数。

如：9=1+3+5；

16=1+3+5+7；

所以，不断的进行奇数相加，并判断x大小即可。代码如下：

public class Solution {
    public int sqrt(int x) {
        int i = 1;
        int res = 0;
        while (x >= 0) {
            x -= i;
            res++;
            i += 2;
        }
        return res - 1;
    }
}

class Solution {
public:
    int sqrt(int x) {//思路用二分法
        if (x < 2)
            return x;
        int left = 1, right = x / 2;    //右端从x/2开始
        int mid, last_mid;
        
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (x / mid > mid) {	//不用x > mid * mid 会溢出
                left = mid + 1;
                last_mid = mid;
            }
            else if (x / mid < mid)
                right = mid - 1;
            else 
                return mid;
        }
        return last_mid;
    }
};

public class Solution {
    public int sqrt(int x) {
		int low = 0;
		int high = x;
		while (low <= high) {
			long mid = (low + high) / 2;
			if(mid * mid == x) return (int)mid;
			else if(mid * mid < x) low = (int)(mid + 1);
			else high = (int)(mid - 1);
		}
		return high;
	}
}

public class Solution {
    //牛顿法思路：
    //r = sqrt(x)，即r*r = x
    //故有f(r) = r*r-x = 0 这里注意r是变量，x是常数
    //按照牛顿迭代法公式 r_new = r_old + f(r)/f'(r)
    //得 r_new = (r_old+x/r_old)/2
    //一般，牛顿法是当 一次迭代的变化量足够小时就停止迭代
    //这里利用了f(r)的特征，将r初始化为x,可以画图查看，r的初始值在sqrt(x)的右半边
    //在循环内的迭代过程中，r始终在sqrt(x)的右半边。直到退出循环得出答案
    public int sqrt(int x) {
        if(x==0 || x==1) return x;
        long r = x; 
        while(x/r<r)//即r*r>x
            r = (r+x/r)/2;
        //此时r*r<=x 即为答案
        return (int)r;
    }
}

//	public static int sqrt(int x) {
//        return (int)Math.sqrt(x);
//    }
但是题的意思不是用这个
特比特别要注意两点：第一right要取x/2+1  这个还不是最重要的，其实只是影响速度
第二：要用x/middle>middle  来表示x>middle*middle  不然会溢出
第三：判断相等时用x/middle>=middle && x/(middle+1)<(middle+1)
public static int sqrt(int x) {
		if(x==0){
			return 0;
		}
		if(x<0){
			return -1;
		}
		int left = 1,right = x/2+1,middle ;
		while(left<=right){
			middle = (left+right)/2;
			if(x/middle>=middle && x/(middle+1)<(middle+1)){
				
				
				return middle;
			}else if(x/middle>middle){
				left = middle+1;
			}else{
				right = middle-1;
			}
		}
		return right;
	}

public class Solution {
    public int sqrt(int x) {
		if (x== 0)
			return 0;
		int left = 1, right = x;
		while (true) {
			int mid = left + (right - left) / 2;
			//这里判断不用if (mid * mid > x)，因为使用mid > x / mid一定会有结果
			if (mid > x / mid)
				right = mid - 1;
			else {
				if(mid+1>x/(mid+1))
					return mid;
				left=mid+1;
			}
		}
	}
}