二分查找,不过查找过程中的判断条件更细一些,比如会判断mid以及mid+1的正确性,贴代码
class Solution { public: int mySqrt(int x) { if(x == 0) return 0; if(x == 1) return 1; long long x_temp = x; long left = 1; long right = x_temp-1; while(left<=right) { long long mid = (left + right)/2; if(mid*mid == x_temp) return mid; else if(mid*mid > x_temp) { right = mid - 1; } else { if((mid+1)*(mid+1) > x_temp) return mid; else if((mid+1)*(mid+1) == x_temp) return mid+1; else { left = mid + 1; } } } return 0; } };
牛顿迭代法,需要数学方面的推导,设定一个函数y = x^2 -c,C开根号值即为该函数正零点,然后通过每一点的切线与x轴的交点不断逼近目标值。贴代码
1 class Solution { 2 public: 3 int mySqrt(int x) 4 { 5 if(x == 0) 6 return 0; 7 double C = x; 8 double x0 = x; 9 while(1) 10 { 11 double x_temp = 0.5*(x0 + C/x0); 12 if(fabs(x_temp-x0)<1e-7) 13 break; 14 x0 = x_temp; 15 } 16 return x0; 17 } 18 };