69.x的平方根

给你一个非负整数x计算并返回x的算术平方根。由于返回类型是整数结果只保留整数部分小数部分将被舍去 。注意不允许使用任何内置指数函数和算符例如pow(x, 0.5)或者x ** 0.5。代码语法1LL表示一个long long类型的整数1它的作用是强制让后面的乘法按照 long long 来计算。如果写long long squaremiddle*middle;虽然左边是long long但是右边的middle*middle可能会先用int计算计算过程中就已经溢出了然后再赋值给long long已经晚了。所以写1LL*middle*middle可以保证整个乘法从一开始就是long long运算。题目的本质找到一个整数ans1.ans*ansx;2.(ans1)*(ans1)x;所以我们可以在[0, x]这个范围里用二分查找找到最大的num使得num*numx;然后分为三个条件判断跟二分法一样有一个要点是最后返回的是right这个就是我们前面说的要满足最大的ans*ansx;结束循环时候此时leftrightright停在最后一个满足right*rightxclass Solution { public: int mySqrt(int x) { int left0; int rightx; while(leftright){ int middleleft(right-left)/2; long long square1LL * middle *middle; if(squarex) return middle; else if(squarex) leftmiddle1; else rightmiddle-1; } return right; } };