个人主页：Lei宝啊
愿所有美好如期而遇
二分算法前言
二分算法原理超详细讲解(包括暴力求解，朴素二分查找，二分查找左右端点)：二分查找(非朴素)--在排序数组中查找元素的第一个和最后一个位置
https://blog.csdn.net/m0_74824254/article/details/135306648?spm=1001.2014.3001.5501
本题链接
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
输入描述
输入一个数，求其平方根，不允许使用sqrt库函数，因为我们要模拟sqrt，
接口为int mySqrt(int x)
输出描述
我们以8为例子，要求8的平方根，根号2明显求不整，所以要去掉小数部分，返回整数部分。
算法分析
算法一：暴力求解
我们直接定义变量 i 从 0 开始for循环遍历，直到平方大于x，我们返回 i - 1。
算法二：二分算法
这个属于查找右端点
我们首先要分区间，一个区间内下标的平方小于等于x，一个区间内下标的平方大于x，我们要的是小于等于区间的最右边那个数的下标。(lhs意为left side hand即左手边，rhs意为right side hand即右手边)
我们定义mid以及num，num = mid * mid代表平方，所以有
- 小于等于区间 ，if(num <= x) lhs = mid;
- 大于区间，if(num > x ) rhs = mid - 1;
那么为什么lhs 不是 mid + 1呢？当我们的mid位于小于等于区间的右边界处，此时lhs = mid + 1,那么lhs就出了小于等于区间，我们也就得不到想要的下标了。
要知道我们可以预见的一个事实就是，lhs是不会越过小于等于区间的，因为只有num <= x，lhs才会更新到mid处，而这样的mid都在区间内，也就是说，只有等到rhs越过大于区间使得lhs == rhs，此时我们循环结束，得到我们想要的下标，我们将其返回。
我们将上面分区间理解后，还没有完，二分算法有一些细节，如果不注意，那么就会出现死循环。
细节一:
while循环,不同于朴素的二分算法，这里循环结束的条件是lhs < rhs，一个原因是没有必要，另一个原因是如果我们选择去判断相等，会出现死循环。
细节二:
mid的值，不同于朴素二分算法，如果我们选择mid = lhs + (rhs - lhs) / 2；同样会出现死循环。
上述两个细节的详细原因我们在二分算法前言的链接里详细提到，这里不多赘述。
解题源码
class Solution {
public:
int mySqrt(int x)
{
//注意范围
long long lhs = 0, rhs = x;
long long mid = lhs + (rhs - lhs + 1) / 2, num = mid * mid;
//细节一
while(lhs < rhs)
{
//分区间
if(num <= x) lhs = mid;
else rhs = mid - 1;
//细节二
mid = lhs + (rhs - lhs + 1) / 2;
num = mid * mid;
}
return lhs;
}
};
