69.md

Leetcode 69. x 的平方根

69. x 的平方根

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  // 除了 1，2，3，4以外，一个数的平方根一定不会超过它的一半
  if (x < 2) {
    return x;
  }

  // 获取计算范围，因为大于4的数，其平方根不会超过它的一半，所以计算范围为 1 - x/2
  let left = 1; // 起始值
  let right = parseInt(x / 2); // 将目标数值除以 2

  // 开始循环处理
  while (left < right) {
    let mid = parseInt(left + (right - left) / 2); // 取计算范围的中间值

    // 如果 mid 的平方大于 x，right = mid - 1，继续计算。
    // 如果 mid 的平方小于 x，left = mid，继续计算。
    // left >= right，循环结束
    // console.log(left, right, mid);
    if (mid * mid > x) {
      right = mid - 1;
    } else if (mid * mid == x) {
      left = mid;
      break;
    } else {
      left = mid + 1;
    }
  }
  if (left * left > x) {
    left--;
  }
  return left;
};

let i = 1;
while (i < 100) {
  console.log(i, mySqrt(i));
  i++;
}