x的平方根

题目：x的平方根给你一个非负整数 x ，计算并返回 x 的 算术平方根 ，由于返回类型是整型，结果只保留整数部分，小数部分将被舍去，要求不允许使用任何内置指数函数和运算符

题目链接：力扣

思想（二分查找）：

1. 二分查找的mid只会出现三种情况：

• 1.mid的值的平方刚好等于x，此时这个值刚好是x的算术平方根；
• 2.mid的值的平方大于x，此时这个值肯定不可能是x的算术平方根；
• 3.mid的值的平方小于x，此时整个值可能是x的算术平方根（因为实际的平方根可能是小数，但是这里只保留整数部分，小数部分舍弃）.

2.定义一个pos变量，每进行一次二分查找之后需要用mid的值去更新pos.

3. 当mid的值的平方小于等于x时，需要更新pos，将mid的值赋给pos（如果刚好等于直接返回pos即可，如果是小于更新完pos之后，还需要更新left的值），当mid的值的平方大于x时，说明mid的值一定不是x的算术平方根，所以需要更新right的值继续进行二分查找！

完整代码（方法一）：

class Solution {public int mySqrt(int x) {int left = 0;int right = x;int pos = -1;//用来存储mid更新之前的下标 即算术平方根while(left <= right) {int mid = left + (right - left) / 2;if((long)mid * mid <= x) {//这里需要注意mid和mid的乘积可能会存在数据溢出的情况，所以需要进行强转//将int类型的数据强转成long类型pos = mid;left = mid + 1;} else {right = mid - 1;}}return pos;
}

 缺陷：上述代码有一个不好的地方就是mid与mid的乘积可能超出int类型所要表示的范围，在和目标元素x比较的时候可能发生溢出的情况，所以这里保险起见，需要强转成long类型的数据！

方法二：

方法二针对方法一的缺陷进行了优化，既然mid和mid的乘积容易发生变化数据溢出的情况，那么这里直接将乘法改成除法（修改判断的条件），但是注意除法的被除数不能为0，所以需要对特殊数据0进行单独判断；

class Solution {public int mySqrt(int x) {//使用 / 可以避免mid*mid越界//需要对特殊数字0进行单独判断if(x == 0) {return 0;}int left = 1;int right = x;int pos = -1;while(left <= right) {int mid = left + (right - left) / 2;if(mid <= x/mid) {pos = mid;left = mid + 1;} else {right = mid - 1;}}return pos;}
}

有效的完全平方数

题目：给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false ；完全平方数 是一个可以写成某个整数的平方的整数；换句话说，它可以写成某个整数和自身的乘积；不能使用任何内置的库函数，如  sqrt 。

题目链接：力扣

思想：

这题可以基于上面求x的算术平方根的思想，使用二分查找，可能出现如下三种情况：

1.mid的值的平方等于num，此时num是一个完全平方数；

2.mid的值的平方小于num，需要继续对区间【mid+1，right】进行二分查找；

3.mid的值的平方大于num，需要继续对区间【left，mid-1】进行二分查找.

完全代码如下（法一）：

class Solution {public boolean isPerfectSquare(int num) {int left = 0;int right = num;while(left <= right) {int mid = left + (right - left) / 2;if((long) mid * mid < num) {left = mid + 1;} else if((long) mid * mid > num) {right = mid - 1;} else {return true;}}return false;
}

缺陷：上述代码有一个不好的地方就是mid与mid的乘积可能超出int类型所要表示的范围，在和目标元素x比较的时候可能发生溢出的情况，所以这里保险起见，需要强转成long类型的数据！

法二：

方法二针对方法一的缺陷进行了优化，既然mid和mid的乘积容易发生变化数据溢出的情况，那么这里直接将乘法改成除法（修改判断的条件），但是注意除法的被除数不能为0，所以需要对特殊数据0进行单独判断；

class Solution {public boolean isPerfectSquare(int num) {//判断特殊数字if(num == 0) {return true;}//对于其余数字进行判断int left = 1;int right = num;while(left <= right) {int mid = left + (right - left) / 2;if(mid < (num*1.0/mid)) {left = mid + 1;} else if(mid > (num*1.0/mid)) {right = mid - 1;} else {return true;}}return false;}
}