【算法|二分查找No.2】leetcode 69. x 的平方根

清疚 2024-04-27 06:55 62阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞? 收藏✨ 留言✉ 加关注?本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[手撕算法系列专栏][Link 2]】【[LeetCode][]】  
> ?本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> ?希望我们一起努力、成长，共同进步。

**原题链接：[点击直接跳转到该题目][Link 3]**

#### 目录 ####

*  1️⃣题目描述
 *  2️⃣代码编写

## 1️⃣题目描述 ##

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

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

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

**示例1：**

> 输入：x = 4  
> 输出：2

**示例2：**

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

![在这里插入图片描述][a9f16c68e2774d4baa7096b2ea21a151.png]

## 2️⃣代码编写 ##

class Solution {
        
    public:
        int mySqrt(int x) {
        
            if(x < 1) return 0;
            int l = 1,r = x;
            while(l < r)
            {
        
                long long mid = l + (r - l + 1) / 2;
                if(mid * mid <= x) l = mid;
                else r = mid - 1;
            }
            return l;
        }
    };

**最后就通过啦！！！**

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[LeetCode]: https://blog.csdn.net/m0_74352571/category_12252087.html
[Link 3]: https://leetcode.cn/problems/sqrtx/
[a9f16c68e2774d4baa7096b2ea21a151.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/206c7e6409f1468282f68ddb0bacdf07.png