X 的平方根

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
  if (x === 0 || x === 1) {
    return x;
  }

  for(let i = 0; i < x; i++) {
    if (i * i <= x && (i + 1) * (i + 1) > x) {
      return i;
    }
  }
};

var mySqrt = function(x) {
  if (x === 0) {
    return x;
  }

  return binarySearch(1, x, x);
};

function binarySearch(low, high, x) {
  if (low >= high - 1) {
    return low;
  }

  const mid = Math.floor((low + high) / 2);

  if (mid * mid > x) {
    return binarySearch(low, mid, x)
  } else {
    return binarySearch(mid, high, x)
  }
}

var mySqrt = function(x) {
  if (x === 0) {
    return x;
  }

  return newton(1, x);
};

function newton(n, x) {
  const result = (x / n + n) / 2;

  if (result === n) {
    return Math.floor(n);
  } else {
    return newton(result, x);
  }
}