二分题，第一遍写起来还是有点问题，记录一下解题思路。
二分一：
开根号，也就是找到 区间为1的low和high，那么low就是答案，因此 while (low+1<high) 来保证区间为1。
维护区间 [low, high], 但是我第一次做的时候，更新high是 high=mid-1，最后返回的是 low，出现了问题。这是因为想的时候 high=mid-1 可以进一步缩小区间，但是答案也可能落在high上，因此最后return的时候要对 low 和 high 做一次判断找出正确答案。
class Solution { public: int mySqrt(long x) { if (x==0 || x==1) return x; long low=0, high=x; while (low+1<high){ long mid = (low+high)/2; if (mid*mid==x) return mid; else if (mid*mid<x) low=mid; else high=mid-1; } return high*high>x?low:high; } };
二分二：
思路和刚刚一样，维护闭区间 [low, high]，唯一不同就是更新 high 的时候 high=mid，保证 high^2>mid，因此 high 绝对不可能是答案，答案只可能是 low。实质就是维护low的过程，low逼近最终的答案；而high是单纯缩小数组的空间。
class Solution { public: int mySqrt(long x) { if (x==0 || x==1) return x; long low=0, high=x; while (low+1<high){ long mid = (low+high)/2; if (mid*mid==x) return mid; else if (mid*mid<x) low=mid; else high=mid; } return low; } };
二分三：upper bound
题目是要寻找 平方小于等于x的数，可以通过做找第一个大于等于x的数，减一得到。而这个问题就是 upper bound的问题，开区间闭区间做都okay。开区间代码如下：
class Solution { public: int mySqrt(long x) { if (x==0 || x==1) return x; long low=0, high=x; while (low<high){ long mid=(low+high)/2; if (mid*mid==x) return mid; else if (mid*mid<x) low=mid+1; else high=mid; } return low-1; } };
三种方法都可以，推荐第三种解法，直接上upper bound，相比一二的方法更容易写。
原文：https://www.cnblogs.com/hankunyan/p/9499084.html