69.Sqrt(x)-Leetcode

我的AC方法（暴力）

class Solution {
public:
    int mySqrt(int x) {
        int i=1;
        while(x/i>=i)
            i++;
        return i-1;
    }
};

最优解法

思想：二分法，每次修改上下边界的值

class Solution {
public:
    int mySqrt(int x) {
        if(x<=1) return x;
        int l=0;
        int h=x;
        long long m=1;
        while(h-l>=0)
        {   
            m=l+(h-l)/2;
           // cout<<"m="<<m<<endl;
            if(m*m==x) return m;
            if(m*m<x)
                l=m+1;
            else
                h=m-1;
           // cout<<"l="<<l<<";h="<<h<<";m="<<m<<endl;
        }
        return h;
    }
};