69. x 的平方根

链接：https://leetcode-cn.com/problems/sqrtx/

题目描述见链接内容。

解法：二分法

因为是在集中练习二分法时做到这道题目，自然而然就想到了使用二分法，按照那个套路：

• while的条件仍然是left < right
• 因为题目要找的平方根，并且只保留整数部分，实际上要找的就是平方小于等于x的最后一个下标，按照套路，if的条件取反，那就是mid * mid > x，这样mid实际上是不需要保留的，所以if下面的缩小规模的公式就是right = mid - 1
• 配套的else中的逻辑就是left = mid
• 因为left = mid出现，所以mid应该向上取值，否则会陷入死循环，无法达成left === right的条件
• 返回left

所以写出代码：

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

  let left = 0,
    right = x;

  while (left < right) {
    const mid = Math.ceil((left + right) / 2);
    if (mid * mid > x) {
      right = mid - 1;
    } else {
      left = mid;
    }
  }
  return left;
};

• 时间复杂度： ${O(logn)}$
• 空间复杂度：${O(1)}$
• 执行用时：96ms，在所有JavaScript提交中击败了84.93%的用户，内存消耗：38.9MB，在所有JavaScript提交中击败了96.67%的用户

我估计自己过一阵子可能会对自己写的又懵逼了，如果懵逼回头看看这篇总结

其他解法

看了官方题解，还有『袖珍计算器算法』和『牛顿迭代法』，我的高数知识、高中数学知识都被狗吃了，我放弃了这两种解法了。