Implement int sqrt(int x). Compute and return the square root of x. http://leetcode.com/onlinejudge#question_69

leetcode_sqrt_x.cpp

class Solution {
public:
    int sqrt(int x) {
        if (x <= 0)
            return 0;
        int ret = 1;
        int left = 1, right = x;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (mid <= x / mid) {
                ret = max(ret, mid);
                left = mid + 1;
            }
            else
                right = mid - 1;
        }
        return ret;
    }
};