69. Sqrt(x) (unsolved)

Implement int sqrt(int x).

Compute and return the square root of x.

解答： 二分查找，计算left，right，mid，然后mid的平方==x就行,主要还得一个个试

class Solution { public: int mySqrt(int x) { if(x==0) return 0; long long left=1,right=x; while(left<=right) { long long mid=(left+right)/2; if(mid*mid==x) return mid; if(mid*mid<x) left=mid+1; else right=mid-1; } return right; } };

二刷的时候，发现假如是double型的数，那么得解决一个问题，就是小于1的数，越开方越大，那么得分开考虑大于1和小于1的情况。假设我们容许的误差范围为error

double squaretoot(double x) { double left,right; if(x<1.0) { left=x;right=1.0; } else { left=1.0;right=x; } while(compare(left,right)==0){ double mid=left+0.5*(right-left); double mid_squared =mid*mid; if(compare(mid_squared,x)==1){ return mid; }else if(compare(mid_squared,x)==2) { right=mid; }else { left=mid; } } int compare(double a,double b) { double diff=(a-b)/b; if(diff<-errror) return 0； else if (diff>error) return 2; else return 1; } }

三刷的时候，虽然自己做出来了，但是太慢了。 做二分查找的时候，注意 0，1，2，3，4，9这几个例子

class Solution { public: int mySqrt(int x) { if(x==0) return 0; if(x==1) return 1; //if(x==2) return 1; int left=0,right=x; while(left<right) { long long mid=left+(right-left)/2; if(mid*mid==x) return mid; else if(mid*mid<x) {left=mid+1; } else {right=mid; } } return left-1; } };