Application of Bisection Method

https://www.gjxhlan.me/2018/07/07/需要转换思路的一些题目/

有些时候，某些题目从不同的角度思考都可以得到正确的结果，但是其时间和空间复杂度却大不一样。

例如一道题可以通过递推去正向求解，但是时间复杂度可能会较高；如果这道题的某些值在一个特定的范围之内，而且我们又可以给出一个采纳或放弃这个解的线性时间的判别条件的话，不妨换个思路直接对解的值采用二分查找的策略，从而可以快速排除一些不需要枚举的状态。

Compute the integer square root
SquareRootInt.java
  public static int squareRoot(int x) {
    if (x <= 1) {
      return x;
    }

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

Compute the real square root

SquareRoot.java
  public static double squareRoot(double x) {
    // Decides the search range according to x.
    double l, r;
    if (compare(x, 1.0) < 0) { // x < 1.0.
      l = x;
      r = 1.0;
    } else { // x >= 1.0.
      l = 1.0;
      r = x;
    }

    // Keeps searching if l < r.
    while (compare(l, r) == -1) {
      double m = l + 0.5 * (r - l);
      double squareM = m * m;
      if (compare(squareM, x) == 0) {
        return m;
      } else if (compare(squareM, x) == 1) {
        r = m;
      } else {
        l = m;
      }
    }
    return l;
  }


  // 0 means equal, -1 means smaller, and 1 means larger.
  private static int compare(double a, double b) {
    final double EPSILON = 0.00001;
    // Uses normalization for precision problem.
    double diff = (a - b) / b;
    return diff < -EPSILON ? -1 : (diff > EPSILON ? 1 : 0);
  }