1. 题目
69. x 的平方根
2. 描述
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去。
3. 实现方法
3.1 方法 1
3.1.1 思路
二分查找
由于 x 的平方根的整数部分 res 是满足 res * res <= x 的最大值，因此对 res 进行二分查找；
确定上下界 low、high，然后比较中间元素 mid 的平方和 x 的大小， 通过结果调整上下界范围；
此时的时间复杂度为需要二分查找的次数，为 O ( l o g n ) O(log n)O(logn)；
3.1.2 实现
public int mySqrt(int x) { int low = 0; int high = x; int res = 0; while(low <= high){ int mid = low + (high - low) / 2; if(x >= (long) mid * mid){ res = mid; low = mid + 1; }else{ high = mid - 1; } } return res; }
