🚩传送门：牛客题目

题目

给定一个非负整数 [NC]32. 求平方根 - 图1，计算并返回 [NC]32. 求平方根 - 图2 的平方根，即实现 [NC]32. 求平方根 - 图3 函数。

要求：

  1. 正数的平方根有两个，只输出其中的正数平方根。
  2. 如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。

示例 1:

输入: x = 4 输出: 2

示例 2:

输入: x = 8 输出: 2 解释: 8 的平方根是 2.82842…，由于小数部分将被舍去，所以返回 2

解题思路：二分法

对于非负整数 [NC]32. 求平方根 - 图4 可以暴力搜索其正数平方根。从 [NC]32. 求平方根 - 图5 开始，计算当前值 [NC]32. 求平方根 - 图6 是否满足 [NC]32. 求平方根 - 图7

  • 成立就输出结果
  • 不成立计算下一个值 [NC]32. 求平方根 - 图8++ 继续判断。

暴力解法的时间复杂度为 [NC]32. 求平方根 - 图9。

🚩这个过程其实可以使用 二分法优化 ，因为根据数学知识可知数字[NC]32. 求平方根 - 图10的平方根一定在区间[NC]32. 求平方根 - 图11，取这个区间的中间值[NC]32. 求平方根 - 图12，并判断[NC]32. 求平方根 - 图13与[NC]32. 求平方根 - 图14的大小关系。

  • 若 [NC]32. 求平方根 - 图15 ，接着判断 [NC]32. 求平方根 - 图16。
    1. - 如果满足  ![](https://cdn.nlark.com/yuque/__latex/c98e4fd77c9fe0dae93d15094dceb941.svg#card=math&code=%5Csmall%20%20%28m%20%2B%201%29%5E%202%20%3E%20n%0A%0A&id=Tuw7U)，那么![](https://cdn.nlark.com/yuque/__latex/4760e2f007e23d820825ba241c47ce3b.svg#card=math&code=m&id=i9Hpd)就是![](https://cdn.nlark.com/yuque/__latex/df378375e7693bdcf9535661c023c02e.svg#card=math&code=n&id=dbSnT)的平方根。
    2. - 如果满足 ![](https://cdn.nlark.com/yuque/__latex/6e0c08ade600644809cf7a6203c63e6e.svg#card=math&code=%5Csmall%20%20%28m%20%2B%201%29%5E%202%20%5Cleq%20n%0A%0A&id=XZ8V3)，则![](https://cdn.nlark.com/yuque/__latex/df378375e7693bdcf9535661c023c02e.svg#card=math&code=n&id=fkvYb)的平方根比![](https://cdn.nlark.com/yuque/__latex/4760e2f007e23d820825ba241c47ce3b.svg#card=math&code=m&id=i0b8X)大，继续搜索 `**[m + 1, n]**`。
  • 若 [NC]32. 求平方根 - 图17，则说明[NC]32. 求平方根 - 图18的平方根比[NC]32. 求平方根 - 图19小，继续搜索 **[1, m - 1]**。

解释代码

  1. class Solution:
  2.     def mySqrt(self, x: int) -> int:
  3.         # 二分法
  4.         if x <= 1: # 
  5.             return x
  6.         left = 0
  7.         right = x
  8.         while left <= right:
  9.             mid = (left+right)//2
  10.             if mid**2 <=x and (mid+1)**2 > x:
  11.                 return mid
  12.             elif mid**2 < x: # 数值偏小，需要扩大
  13.                 left = mid + 1
  14.             elif mid**2 > x: # 数值偏大，需要缩小
  15.                 right = mid - 1

我的代码

  1. class Solution {
  2.     public int mySqrt(int x) {
  3.         int left = 1;
  4.         int right = x;
  5.         while (left <= right) {
  6.             // 1.不可使用 (left+right)/2 原因:left+right 可能溢出int
  7.             int mid = left + ((right - left) >> 1);
  8.             // 2.不可使用 mid*mid  原因:mid*mid 可能溢出int
  9.             if (mid <= x / mid) {
  10.                 if (mid + 1 > x / (mid + 1)) {
  11.                     return mid;
  12.                 }
  13.                 left = mid + 1;
  14.             } else {
  15.                 right = mid - 1;
  16.             }
  17.         }
  18.         return 0;
  19.     }
  20. }