# 3.x的平方根(easy)

TIP

更好的阅读体验应该是:

  1. 审题-思考
  2. 答题
  3. 整理-归纳

# 一、题目

LeetCode:69.x 的平方根 (opens new window)

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

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

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

# 二、二分法解题

二分查找是一种基于比较目标值和数组中间元素的教科书式算法。

  • 如果目标值等于中间元素,则找到目标值。
  • 如果目标值较小,继续在左侧搜索。
  • 如果目标值较大,则继续在右侧搜索。

时间复杂度:O(logN)。 空间复杂度:O(1)

分析模版

  • 我们的目标是找到平方最接近目标数字的值
  • 相对于基础模版,我们要知道的数字是逼近目标值的,即 mid * mid <= target,大家是否感觉这道题和上一题几乎一模一样~

Javasciprt 代码

var mySqrt = function(x) {
  // 确定条件,k方 <= x
  let min = 1; // 左边界
  let max = x; // 右边界
  let temp = 0; // 存储结果值,因为它会逐渐逼近最终结果
  while (min <= max) {
    let mid = min + ((max - min) >> 1);
    if (mid * mid <= x) {
      // 这里mid * mid = x 时,我仍然移动了左边界,并且跳过的mid,不要怕
      // 它被保存在了temp中,知道返回它或被新的元素覆盖
      temp = mid;
      min = mid + 1; // 忽略左测区间
    } else {
      max = mid - 1; // 忽略右侧区间
    }
  }
  return temp;
};

# 三、写在最后

本文是二分查找-模版 I 的第三题,仅仅是修改与目标值之间的关系,我们一鼓作气拿下下一道题吧!

如果对你有所帮助不妨给本项目的github 点个 star (opens new window),这是对我最大的鼓励~

关于我

  • 花名:余光
  • WX:j565017805
  • 沉迷 JS,水平有限,虚心学习中

其他沉淀

Last Updated: 8/6/2021, 6:58:15 PM