69. x的平方根
题目链接点我！！！
本质上还是二分查找，有两种情况

1. 有整数平方根的，比如16的平方根为4
2. 没有整数平方根的，比如8的平方根为2.82

对于情况1，相当于用二分查找在序列：1，2，3，…，16的中找4，是可以找到的。
对于情况2，相当于用二分查找在序列：1，2，3，…，8中找按升序插入“2.82”的位置，这也是为什么最后返回的是left-1，而不是left。（要在一个非递减序列中插入一个值，使序列保持非递减，该值的插入位置是left），因为二分查找结束后，left指向“3”，而返回值因该是“2.82”的整数部分即“2”。

class Solution {
public:int mySqrt(int x) {int left = 0, right = x/2;//设置左右边界，right可以设为x，这里设为x/2可以更快一些。if (x == 1 || x == 0)//特殊情况处理，可以不写。return x;        while (left <= right) {long mid = left + (right - left)/2;//防止溢出，（left+right）/2，这种写法，对于一种极端情况，如：right很大，left = right-1，那么left+right就会溢出，这里mid为long是因为后边是mid*mid，int会溢出。if (mid * mid > x) right = mid - 1;else if (mid * mid < x)left = mid + 1;elsereturn mid;}return left - 1;}
};

367. 有效的完全平方数
题目链接点我！！！
和上一题相同，分两种情况

1. 有整数平方根的，比如16的平方根为4
2. 没有整数平方根的，比如8的平方根为2.82

对于情况1，可以从序列1，2，3，…，16中找到16的平方根4。即返回true。
对于情况2，则无法从序列1，2，3，…，8中找到2.82。即返回false。

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