69.x的平方根

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

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

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

代码语法：1LL表示一个long long类型的整数1；

它的作用是：强制让后面的乘法按照 long long 来计算。

如果写：

long long square=middle*middle;

虽然左边是long long，但是右边的middle*middle

可能会先用int计算，计算过程中就已经溢出了，然后再赋值给long long，已经晚了。

所以写：

1LL*middle*middle

可以保证整个乘法从一开始就是long long运算。

题目的本质，找到一个整数ans：

1.ans*ans<=x;

2.(ans+1)*(ans+1)>x;

所以我们可以在[0, x]这个范围里，用二分查找找到最大的num，使得：

num*num<=x;

然后分为三个条件判断，跟二分法一样

有一个要点是最后返回的是right，这个就是我们前面说的要满足最大的ans*ans<=x;

结束循环时候此时left>right

right停在最后一个满足right*right<=x

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