2021/04/24 - Leetcode#69 x 的平方根

[lxinr]

题目

实现 int sqrt(int x) 函数。

计算并返回x的平方根，其中x是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例1:

输入: 4
输出: 2

示例2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

方法一: 使用Math方法

// 取幂
function mySqrt(x) {
  if(x === 0 || x === 1) return x
  return Math.floor(Math.pow(x, 0.5))
}
// 直接平方
function mySqrt(x) {
  if(x === 0 || x === 1) return x
  return Math.floor(Math.sqrt(x))
}

当然这么写就没有任何意义了，能被拍死!

方法二：二分查找

思路

从示例中可以看出，平方根的值如果是个小数，则会将小数部分舍去，即Math.floor(x)，因此我们可以得到：

• 一个数$T_r$的平方如果大于被平方的数$X$，则$T_r$肯定不可能是$X$的平方根
• 因此$X$的平方根的范围必然在$[0..T_r]$之间
• 二分，取得中间值$T_l$，如果$T_l$的平方小于$X$，则$X$的平方根的范围为$[T_l..T_r]$，反之则为$[0..T_l]$
• 重复，直到发现一个临界值$T_l$为$X$的平方根

边界场景

1. 针对 $0$ 和 $1$ 这两个特殊的值，可以特殊判断直接返回
2. 一般来说，可以想到的是一个数$X$的平方根，肯定不会大于$X/2$，但也有例外，如$1$，$2$，$3$，但因为都会取整，因此也没有什么关系，所以总体来说就是下界为$1$，上界为$X/2$

代码实现

function mySqrt(x) {
  if(x === 0 || x === 1) return x

  let left = 1
  let right = Math.floor(x / 2)

  while(left < right) {
    // 获取中位数，此时向上取整
    let m = Math.ceil(left + (right - left) / 2)
    // 如果使用乘法即m * m > x来判断就有可能出现溢出的情况，因此改用除法
    // 如果区间中位数的平方大于x，则表明结果应该是在m的左侧区间
    // 如果相等，则返回中位数
    if(m === x / m) return m
    if(m > x / m) {
      right = m - 1
    } else {
      // 小于的话则表明在右侧区间
      left = m
    }
  }
  return left
}