老师,res=m,为什么要放在else{}里面呢?

在网上看过他写的牛顿迭代法那段代码，大神写代码的思路和普通人完全不一样

老师问下 为啥f（xn）=x^2n-y0 这里有困惑 求指点

这一节很有意思

solution 1: binary search time complexity $O(log^n)$ ```Java float mSqrt(int x, double epsilon) { if (x < 0) return -1; if (x == 0 || x == 1) return x; float left = 0, right = x; while (left <= right) { float mid = left + (right - left) / 2; if (Math.abs(mid - x / mid) < epsilon) return mid; if (mid < x / mid) left = mid; if (mid > x / mid) right = mid; } return Float.NEGATIVE_INFINITY; } ``` solution 2: Isaac newton iterative method time complexity $O(log^n * F(n))$ http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity ```Java float sqrtNewton(int x, double epsilon) { if (x < 0) return Float.NaN; if (x == 0 || x == 1) return x; float iterativeResult = x; while (Math.abs(iterativeResult - x / iterativeResult) > epsilon / iterativeResult) { iterativeResult = (x / iterativeResult + iterativeResult) / 2; } return iterativeResult; } ```

sicp上有一个求平方根的介绍，用的就是牛顿迭代法

除2，可以用位运算，右移一位性能更好

public int sqrt(int x) { if (x == 0 || x == 1) { return x; } int left = 1, right = x - 1, res = 0; while (left <= right) { int mid = (left + right) / 2; int div = x / mid; if (div == mid) { return mid; } else if (div > mid) { left = mid + 1; res = mid; } else { right = mid - 1; } } return res; } public double sqrt(int x, int scale) { int sqrtInt = sqrt(x); if (sqrtInt * sqrtInt == x) { return sqrtInt; } int exp = -1 * scale; double result = sqrtInt; for (int i = -1; i >= exp; i--) { int l = 1, r = 9; double res = 0; double pow = Math.pow(10, i); while (l <= r) { int m = (l + r) / 2; double part = m * pow; double sqrtDouble = result + part; double cur = sqrtDouble * sqrtDouble; if (cur > x) { r = m - 1; } else { l = m + 1; res = part; } } result += res; } return result; } @Test public void test() { double sqrt = sqrt(2, 6); System.out.println(sqrt); System.out.println(sqrt * sqrt); }

老师， (l+r)/2会有溢出风险，用l + (r/2)是不是更稳妥

69. x 的平方根 超哥的板书+大神的参考答案 //binary search int mySqrt(int x){ if (x == 0 || x == 1) return x; int l = 1, r = x, res; while (l <= r) { int mid = (l + ((r-l) >> 1)); if (mid == x/mid) { return mid; }else if (mid > x/mid) { r = mid - 1; }else { l = mid + 1; res = mid; } }return res; } //Newton int mySqrt(int x){ if ((x == 1) || (x == 0)) return x; else { int n1 = x>>1, n2 = x>>1; do { n1 = n2; n2 = (n1 + x/n1)>>1; }while(n1 > n2); return n1; } } #binary search class Solution: def mySqrt(self, x: int) -> int: if x == 1: return 1 l, r = 0, x while l <= r: mid = l + ((r-l)>>1) if mid * mid <= x < (mid+1) * (mid+1): return mid elif x < mid * mid: r = mid else: l = mid #Newton class Solution: def mySqrt(self, x: int) -> int: x_previous = x x_current = x / 2 precision = 0.1 while abs(x_previous - x_current) > precision: x_previous = x_current x_current = (1/2) * (x_current + x/x_current) return int(x_current)