69.x的平方根：
你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留整数部分 ，小数部分将被 舍去 。注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
链接：https://leetcode.cn/problems/sqrtx
示例 1:
输入：x = 4
输出：2
示例 2:
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 231 - 1
初步思考：（二分查找）
关键词：只保留整数部分。
这就给我们带来了思路，求解的整数ans满足表达式ans*ans<=x，因而我们可以将x前的数看作是一个数组，进行二分查找进而获得答案。
这里使用的是左开右开形二分查找：
左开右开：
int mySqrt(int x) {
int left = 0;//考虑0的情况
int right = x / 2 + 2; //考虑1的情况
while (left + 1 != right)
{
int mid = left + (right - left) / 2;
if (mid <= x / mid) //使用除法避免溢出（乘法会溢出）
{
left = mid;
}
else
{
right = mid;
}
}
return left;
}
利用左开右开区间的好处在于：不同特地再去讨论x=0或x=1的特殊情况。同时，该题也很容易出现内存溢出的问题，所以此处采用了用除法代替乘法的方式，防止内存溢出。
该算法的执行用时出奇得低。
当然，该题同样可以使用左闭右闭以及左闭右开的二分查找进行求解。
左闭右开：
int mySqrt2(int x) {
// 先对特殊值进行判断
if (x == 0) {
return 0;
}
if (x == 1) {
return 1;
}
int left = 1;
int right = x / 2;
// 左闭右开
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (mid > x / mid) {
right = mid - 1;
}
else {
left = mid;
}
}
return left;
}
进一步思考：（数学方法）
在LeetCode官方题解中还有着两种数学方法的求解方式，这里就不多加介绍，比较主要使用的数学公式以及方法，属于一种聪明的暴力求解法。
这部分代码来源于LeetCode题解：
链接：https://leetcode.cn/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/
指数算法：
int mySqrt(int x) {
if (x == 0) {
return 0;
}
int ans = exp(0.5 * log(x));
return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);
}
该种算法的时间复杂度以及空间复杂度都可以视作为O（1），但是运用了内置的个exp函数以及log函数
牛顿迭代法：
借助了泰勒级数，从初始值开始快速向零点逼近。
int mySqrt(int x) {
if (x == 0) {
return 0;
}
double C = x, x0 = x;
while (true) {
double xi = 0.5 * (x0 + C / x0);
if (fabs(x0 - xi) < 1e-7) {
break;
}
x0 = xi;
}
return int(x0);
总的来说，该题的难点在于发现题目中的要求是取整数值，进而可以想到运用二分查找的方法进行求解。
以后也会坚持持续更新的我LeetCode学习笔记，分享我所学到的以及我个人的思考，欢迎和我一起来交流。
CSDN同步更新，欢迎关注我的博客：一粒蛋TT的博客_CSDN博客-LeetCode学习笔记,HTML+CSS+JS,数据结构领域博主
