【LeetCode】 69 x的平方根

解题思路：
1 这题思路很简单，坑比较多，可以从判断条件，遍历方式等去优化
2 最先想到的一定是判断条件：i * i < x && (i+1) * (i+1) > x.
3 其次就会想到，很粗暴的遍历。会出现两个问题：①太慢②int溢出
4 判断条件优化：改为除法，即 x / i < i，避免了溢出；
5 遍历优化：改为二分法；
6 另外，还有牛顿开方法，完全是数学问题，不具有共性；随便说一下，牛顿开方法其实就是，对 y = x^(1/2)进行牛顿迭代找根。牛顿迭代的思想就是对某个x对应的f(x)处做切线，切线与x轴相交的点就是下一个迭代用的x。循环迭代，直到f(x)逼近0，此处的x即为较为精准的解。

代码（二分法）：

class Solution {
    public int mySqrt(int x) {
        int high = x;
        int low = 1;
        
        int mid = (low+high)/2;
        for(;low<=high;){
            if (x / mid < mid)
                high = mid-1;
            else if (x/mid > mid)
                low = mid+1;
            else
                return mid;
            mid = (low+high)/2;
        }
        return low-1;
    }
}