85.x的平方根（力扣）

目录

问题描述

代码解决以及思想 

知识点

---

问题描述

代码解决以及思想 

class Solution {
public:
    int mySqrt(int x) {
        int left = 0;            // 定义左边界
        int right = x;           // 定义右边界，初始值取 x
 
        while (left <= right) {  // 当左边界小于或等于右边界时，执行循环
            int middle = left + (right - left) / 2;  // 计算中间值，避免整数溢出
            int midSquare = middle * middle;         // 计算中间值的平方
 
            if (midSquare == x) {  // 如果中间值的平方等于 x，表示找到平方根
                return middle;
            } else if (midSquare > x) {  // 如果中间值的平方大于 x，目标在左半部分
                right = middle - 1;     // 更新右边界
            } else {                   // 否则，目标在右半部分
                left = middle + 1;      // 更新左边界
            }
        }
 
        return left - 1;  // 循环结束后，返回 left - 1，因为 left 已经大于 right，left - 1 的平方是小于等于 x 的最大整数
    }
};

1. 初始化左边界 left 为0和右边界 right 为 x。因为平方根不会大于 x，所以 right 初始值取 x。

2. 进入一个循环，只要 left 不大于 right，执行以下操作：

   a. 计算中间值 middle，通过 (left + right) / 2 来避免整数溢出。

   b. 计算 middle 的平方 midSquare，即 middle * middle。

   c. 检查 midSquare 与 x 的关系：

   • 如果 midSquare 等于 x，表示找到了平方根，返回 middle。
   • 如果 midSquare 大于 x，说明平方根在 left 和 middle 之间，将 right 更新为 middle - 1。
   • 如果 midSquare 小于 x，说明平方根在 middle 和 right 之间，将 left 更新为 middle + 1。

3. 循环结束后，返回 left - 1，因为 left 已经大于 right，而 left - 1 的平方是小于等于 x 的最大整数。

知识点

这个方法利用了二分查找的思想，通过逐步缩小搜索范围来找到满足条件的整数解，即非负整数 x 的算术平方根。这样可以在较快的时间内找到答案。

82.二分查找-CSDN博客

写在最后：以上就是本篇文章的内容了，感谢你的阅读。如果感到有所收获的话可以给博主点一个赞哦。如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~