Leetcode 69. x 的平方根

题目描述：

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:
输入: 4
输出: 2

示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去

问题分析：

实现 int sqrt(int x) 函数。
根据这个题目的要求，需要求的是一个数的平方根的下限，有三种方案：
(1)第一种方法：直接使用JAVA的库函数Math.sqrt()求出一个数的平方根，然后向下取整。向下取整有两种方法，直接使用int强转，或者使用Math.floor(),就可以得到最后的平方根的下界。但是题目叫我们实现sqrt函数，直接调用库函数，显得没什么意思。
(2)第二种方法：定义一个变量从0开始自增，每次求这个变量的平方，如果平方小于等于给定的数，变量自增1，循环结束时说明变量的平方一定是大于给定的数的。分析一下：如果给定的数是完全平方数，例如25，那么最后变量的值为6，实际平方值为5，我们需要的值是5，将变量自减，然后再返回；如果给定的数不是完全平方数，例如28，最后变量的值为6，实际平方值为5.292，我们需要的值是5，将变量自减。在两种情况下都是最终将变量的值自减。时间复杂度是线性级别的。
(3)第三种方法：类似于猜数游戏，给定一个范围1-100，让你猜测给出的数是多少时，最简单的方法就是一直将区间折半，这样比盲目的从头猜要快得多。这里求平方根也可以用这种思想，比如说给定一个数38，先猜测(38+0)/2+1即20是它的平方根(为什么是20不是19也是有原因的，我们最终需要的值是平方根向下取整的值，如果猜测的数的平方大于给定的数，需要向下减1，与之类似，右界限也是要-1的；正好小于的时候，左界限变为猜测值)；显然，需要再猜(19+0)/2+1即10是平方根，右界限变为9，左界限不变；再猜测(9+0)/2+1即5是平方根，左界限变为5，右界限还是9；再猜测(9+5)/2+1即8是平方根，左界限5，右界限7；再猜测(5+7)/2+1即7为平方根，左界限为5，右界限为6；再猜测(5+6)/2+1为平方根，左界限为6，右界限为6，两个界限重合，最终退出循环，得到平方根下限为6。时间复杂度是对数级别的，提升还是有蛮高。

代码实现：

方法1：

	public static int mySqrt(int x){
   
		return 
1
2