数据结构与算法–69.x 的平方根

题目描述

题目链接：x的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
>案例1：
输入：x = 4
输出：2
>案例2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

思路1

首先我想到的解法是最为简单粗暴的暴力求解，对于题目而言，首先考虑特殊的取值（0，1，2），排除特殊取值之后我们采用for循环遍历目标值的一半的每个取值就肯定可以找到需要求解的数值。

class Solution:
    def mySqrt(self, x: int) -> int:
       
        mid = x // 2
        if(x == 1 or x == 0):
            return x
        
        for i in range(mid+1):
            if (i*i <= x < (i+1)*(i+1)):
                return i

结果如下：

思路2

对于本题可以采用二分算法，二分算法左右边界是否封闭等等考虑在内，其次我们需要知道二分算法的最终输出的中间值mid如果没有找到那么肯定最终的输出值是右边；结束条件right一定小于left，所以返回right。

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if(x == 0):
            return 0
        if(x <= 2):
            return 1

        l = 0
        r = x
        while(l <= r):
            mid = (l + r) // 2
            if(mid < x/mid):
                l = mid + 1
            elif(mid > x/mid):
                r = mid -1
            else:
                return mid
        return r

结果如下：

参考
https://leetcode-cn.com/problems/sqrtx/
https://blog.csdn.net/qq_44790423/article/details/109274835