leetCode 69. x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

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

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

一、暴力求解

1. 我们只需定义一个变量每次令该变量的平方与x比较,逐步逼近
2. 等于 直接返回
3. 大于返回 a-1

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    for(let a = 0; a <= x; a++){
        if(a * a > x){
            return a - 1
        }else if(a * a === x){
            return a
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

二、二分查找

1. 假设有一个区间为[0,x],算术平方根也在这个区间之内,所以我们可以使用二分查找法逐步缩小这个区间范围,最后锁定算术平方根的位置
2. 定义变量 left = 0; right = x, mid
3. 循环条件为 left + 1 !== right
4. 在每次循环中先令 let mid = Math.floor((right - left) / 2) + left
5. 随后判断若 mid * mid > x, 说明算术平方根应该在mid左边,也就是[left,mid)区间中,于是我们令right = mid
6. 若 mid * mid < x, 说明算术平方根应该在mid右边,也就是(mid ,left],于是我们令left = mid
7. 若 mid * mid == x, 说明mid正好是算术平方根,直接返回mid即可
8. 随着区间不断缩小,最后left + 1= right,此时算术平方根区间在(left, right)中,因为要舍去小数所以直接返回left即可

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if(x < 2){
        return x
    }
  let left = 0 , right = x
  while( left + 1 !== right ) {
      let mid = Math.floor((right - left) / 2) + left
      if(x / mid < mid){
          right = mid 

      }else if(x / mid > mid){
          left = mid 

      }else{
          return mid
      }
  }


  return left

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26