69. Sqrt(x)

Version 1
61.32 %
class Solution {
    public int mySqrt(int x) {
        if (x <= 1) return x;
        int start = 1;
        int end = x;
        int mid;
        while (start <= end) {
            mid = start + (end - start) / 2;
            if (mid == x / mid) return mid;
            if (mid < x / mid) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return end;
    }
 
}


Version 2
98.32 %

Find the critical point that mid^2 <= x and (mid + 1)^ > x

class Solution {
    public int mySqrt(int x) {
        long start = 0;
        long end = x;
        long mid = 0;
        while (start < end) {
            mid = start + (end - start) / 2;
            if (mid * mid <= x && (mid + 1) * (mid + 1) > x) {
                return (int)mid;
            } else if (mid * mid > x) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        if (start == end) {
            return (int)start;
        } else {
            return (int)end;
        }
    }
}

二刷
12.20 %
class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        long start = 0;
        long end = x;
        while (start < end) {
            long mid = start + (end - start) / 2;
            if (mid * mid <= x) {
                if ((mid + 1) * (mid + 1) > x) {
                    return (int)mid;
                } else {
                    start = mid + 1;
                }
            } else { // mid * mid > x
                end = mid - 1;
            }
        }
        return (int)start;
    }
}

Version 3
mid * mid <= x
-> (x / mid) < actual x / mid
所以 mid * mid <= x can't guarantee that mid <= x / mid
however mid * mid > x can guarantee that mix > x / mid
 96.02 % 

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        int start = 1;
        int end = x;
        int mid = 0;
        while (start < end) {
            mid = start + (end - start) / 2;
            // mid^2 > x
            if (mid > x / mid) {
                end = mid - 1;
            } else {
                // (mid + 1)^2 > x
                if ((mid + 1) > x / (mid + 1)) {
                    return mid;
                } else {
                    start = mid + 1;
                }
            }
        }
        // mid       
        // start end
        return start;
    }
}