☆打卡算法☆LeetCode 69、Sqrt(x) 算法解析

一、题目

1、算法题目

“给定一个非负整数，计算并返回x的算术平方根。”

题目链接：

来源：力扣（LeetCode）

链接：69. Sqrt(x) - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

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

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：
输入： x = 4
输出： 2

示例 2：
输入： x = 8
输出： 2
解释： 8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

二、解题

1、思路分析

这道题，一般有两种思路，第一种使用其他的数学函数代替平方根从而得到结果，第二种是通过数学方法得到近似结果。

第一种没什么好说的，可以将：

\sqrt {x}改成自然幂的形式x1/2，再使用自然对数e进行换底，即可得到：

\sqrt {x} = x1/2 = (eln x)1/2 = e \frac 12ln x

第二种，可以使用二分查找，二分查找的下界为0，比较中间元素的平方与x的大小关系，并通过比较的结果调整上下界的范围。

由于所有的运算都是整数运算，不会存在误差，因此得到的答案就是最终答案。

2、代码实现

代码参考：

public class Solution {
    public int MySqrt(int x) {
        int low = 1;
        int high = x / 2 + 1;
        while(low <= high){
            int middle = (low + high) / 2;
            if(middle < x / middle){
                low = middle + 1;
            }else if(middle > x / middle){
                high = middle - 1;
            }else{
                return middle;
            }
        }
        return high;
    }
}

image.png

3、时间复杂度

时间复杂度 ： O(log x)

既为二分查找需要的次数。

空间复杂度： O(1)

只需要常数级别的空间存放变量。

三、总结

这题目比较特殊，不是准确的二分查找

因为目标出现在，+1就大于条件的最后一个小于条件的位置，参考给定例子

首先我们以0和x为下界和上界，while条件我们用l小于等于r来保证对0的一致性处理

当m的平方小于等于x时候，我们就提高下界

此时，由于我们要求+1就大于条件的最后一个小于条件的位置

所以我们不断更新res

否则，我们缩小上界限