链接：https://leetcode-cn.com/problems/sqrtx
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
这道题是一道经典的用二分来解的题，二分有两个模版，当所求的性质在右边的时候，用模版1，当所求性质在左边的时候，用模版2.
二分的流程是首先定义解所在区间的边界，在这道题中，l = 0, r = x. 然后编写二分的框架，其实是求mid的运算。然后设计一个检查性质是否满足的条件，这个条件一定要满足答案在性质的边界点上。我们用 result <=x , 当result在[0, 向下取整(sqrt(x))]的范围时，性质满足，当result在[向下取整(sqrt(x))+1, x]的范围时，性质不满足，因此check函数是符合条件的。然后判断一下区间如何更新，在这道题中所求的性质在左边，因此我们用模版2，所以更新方式为l = mid, r = mid - 1。并且当使用模版2时，在算mid的时候要加上1。
1 class Solution { 2 public: 3 int mySqrt(int x) { 4 int l = 0, r = x; 5 while(l < r){ 6 int mid = l + (long long)r + 1 >> 1; 7 if(mid <= x / mid) l = mid; 8 else r = mid - 1; 9 } 10 return r; 11 } 12 };
这个代码要注意的地方还是挺多的，一个是在check函数的地方，第7行中如果用mid * mid <= x 会出现溢出的情况，另一个是在第6行，当r = x 时，mid也会出现溢出的情况，所以要把r的数据类型改成long long。最后要注意的地方是右移符号，如果不熟练，很容易写成左移。一个记忆的窍门是，箭头指向哪边，就往哪移，而且记得除以2是右移一位！