二分查找实现平方根计算

1、我们仅需要整数部分
2、mid*mid考虑溢出，left + right也要考虑溢出
3、主要的思想就是k^2 < x 中k的最大取值
4、其实还有很重要的一点while（）,这个括号中应该写什么

二、
我们直接上代码，然后再一步一步解析。

class Solution {
	public int mySqrt(int x) {
		if(x == 0) return 0;
		if(x == 1) return 1;
		int left = 0;
		int right = x;
		int res = 0;
		while(right - left > 1) {
			int mid = (right - left) / 2 + left;
			if(x / mid < mid) {
			right = mid;
			}else {
			left = mid;
			res = left;
		}
	}
	return res;
	}
}

三、
1、我们直接将x=1和x=0这种情况返回
2、while（）中，一般我们会写left < right ,left <= right,其实这里是没有必要的，
因为我们发现，如果left和right相邻，那么结果一定是left。
因为我之前说过是求k^2 < x的最大值，所以right * right是一定大于x的。
故我们只需要记录下left跳出循环的最大值即可。
跳出循环的left的最大值就是x的平方根。