x 的平方根（二分查找）
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去。原函数
1int mySqrt(int x) {
2
3}来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sqrtx
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
实现代码
1int mySqrt(int x)
2{
3 if (x < 2)
4 return x;
5
6 long left = 0, right = x, mid = 0;
7 while (left <= right)
8 {
9 mid = (left + right) / 2;
10 if (mid * mid == x)
11 return (int)mid;
12
13 else if (mid * mid < x)
14 left = mid + 1;
15
16 else
17 right = mid - 1;
18 }
19 return (int)right;
20}
作这题时第一时间想到的是利用 for 来逐个寻找根数，但很快就被否决了。因为 for 的时间复杂度为 o(n)，而且迭代步长如果很小的话，具体的运行时间也会大幅增加；如果步长稍微大一点，那么答案就很大几率会出错；所以多种情况综合考虑，还是使用了二分查找。
二分查找时间复杂度为 O(logn)，明显比用 for 逐个循环要好得多，而且找到的结果更加准确。
二分查找类似递归，想要写好二分查找就要找准结束条件，这一题中的结束条件就是最小值不大于最大值。
之前也有 leetcode 题是介绍的二分查找和递归的，可以看推荐阅读。