二分查找算法(3)

二分查找算法(3) _x的平方根

个人主页：C++忠实粉丝
欢迎点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝原创

二分查找算法(3) _x的平方根

收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌

温馨提示:

1. 题目链接:

2. 题目描述 :

3. 解法 (二分查找):

算法思路:

代码展示:

结果分析:

4. 二分算法模板总结

温馨提示:

这道题是直接使用了二分模板,轻松拿捏了这道题,如果你还不知道的话,自行去下篇博客

---二分查找算法(2) _在排序数组中查找元素的第一个和最后一个_模板-CSDN博客

1. 题目链接:

OJ链接: x的平方根

2. 题目描述 :

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

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

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

示例 1：

输入：x = 4
输出：2

示例 2：

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

提示：

0 <= x <= 231 - 1

3. 解法 (二分查找):

算法思路:

设x的平方根的最终结果为index

分析index左右两次数据的特点:

[1, index]之间的元素, 平方和之后都是小于等于x的;

[index + 1, x]之间的元素, 平方之后都是大于x的

因此可以使用二分查找算法

代码展示:

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

结果分析:

这个算法实现了求一个非负整数x 的平方根，采用了二分查找法。以下是分析：

1. 初始化：当x < 1 时，直接返回 0。否则，初始化 left 为 1，right 为x。

2. 二分查找：

使用 while (left < right) 循环，确保在 left 和 right 之间进行查找。
计算中间值 mid，并使用 long long 来避免溢出。
如果 mid* mid 小于或等于x，则将 left 移动到 mid，表示可能的平方根在右半边。
否则，将 right 移动到 mid - 1，表示平方根在左半边。

3. 返回值：最后返回 left，它是x 的整数平方根。

优点：
时间复杂度：O(log x)，效率高。
准确性：通过调整 left 和 right，能准确找到最大的整数平方根。

4. 二分算法模板总结

这里再次强调一下我们的二分算法模板(真的很好用!!!)

while(left < right){int mid = left + (right - left) / 2;if(...) left = mid + 1;else right = mid;
}while(left < right){int mid = left + (right - left + 1) / 2;if(...) left = mid;else right = mid - 1;
}