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 的最大整数
    }
};

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

进入一个循环，只要 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。

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