69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

问题：实现sqrt函数

思想：任何数x的平方根范围在1~x/2+1，mid*mid<=x&&(mid+1)(mid+1)<x时则mid即为x的平方根

可以利用递归方法 left=1, right=x/2+1， 如果mid*mid>n 则返回 sqrt(x,left,mid-1)，反之返回sqrt(x,mid+1,right)

public int mySqrt(int x) { if(x<0)return -1; if(x==0||x==1) return x; return sqrt(x,1,(x/2+1)); } public int sqrt(int n,long left,long right){ long mid=left+(right-left)/2; if(mid*mid<=n&&(mid+1)*(mid+1)>n) return (int)mid; else if(mid*mid>n) return sqrt(n,left,mid-1); else return sqrt(n,mid+1,right); } 2.还可以利用二分查找方法进行计算，注意循环条件left<=right，因为当二者相等时可能还没有找到平方根，比如x=8，初始left=1，right=5

mid=3,不符条件循环 right=2  mid=1  此时不满足if中的条件， left=mid+1=2  如果不继续进行则输出结果为1，错误

public int mySqrt(int x) { if(x<0) return -1; if(x==0||x==1) return x; long left=1; long right=x/2+1; long mid=0; while(left<=right){ mid=left+(right-left)/2; if(mid*mid<=x&&(mid+1)*(mid+1)>x) return (int) mid; else if(mid*mid>x) right=mid-1; else left=mid+1; } return (int)mid; }