69. x 的平方根

思路

• 整数 x 的平方根一定小于或等于 x
• 除 0 之外的所有整数的平方根都大于或等于 1
• 整数 x 的平方根一定是在 1 到 x 的范围内，取这个范围内的中间数字 mid，并判断 mid 的平方是否小于或等于 x，如果 mid 的平方小于 x
• 那么接着判断(mid+1)的平方是否大于 x，如果(mid+1)的平方大于 x，那么 mid 就是 x 的平方根
• 如果 mid 的平方小于 x 并且(mid+1)的平方小于 x，那么 x 的平方根比 mid 大，接下来搜索从 mid+1 到 x 的范围
• 如果 mid 的平方大于 x，则 x 的平方根小于 mid，接下来搜索 1 到 mid-1 的范围
• 然后在相应的范围内重复这个过程，总是取出位于范围中间的 mid

代码实现

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  let left = 0,
    right = x
  // 左闭右闭区间
  while (left <= right) {
    let mid = left + ((right - left) >> 1)
    if (mid * mid < x) {
      left = mid + 1
    } else right = mid - 1
  }
  return left * left > x ? left - 1 : left
}