s4553711
5/8/2017 - 2:53 PM

69.cpp

class Solution {
public:
    int mySqrt(int x) {
        if (x == 1) return 1;
        long left = 0, right = x;
        long mid = left + (right - left)/2;
        while (left+1<right) {
            if (x > mid*mid) {
                left = mid;
            } else if(x < mid*mid) {
                right = mid;
            } else {
                return mid;
            }
            mid = left + (right - left)/2;
        }
        return left;
    }
};