Sqrt(x)

Q:
mplement int sqrt(int x).
Compute and return the square root of x.

T:
Binary search. Note that we use x/m for comparing.

A:

class Solution {
public:
    int sqrt(int x) {
        if (x < 2) {
            return x;
        }
        int l=0; 
        int r = x;
        int res = l;
        while(l<=r) {
            int m = (l+r) / 2;
            if (m == x/m) {
                return m;
            } else if(m < x/m) {
                l = m+1;
                res = m;
            } else {
                r = m-1;
            }
        }
        return res;
    }
};