69. Sqrt(x) (https://leetcode.com/problems/sqrtx/submissions/): Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

69. Sqrt(x) (#1 Binary search + long type).java

class Solution {
    public int mySqrt(int x) {
        //Solution #1: Cast to long type to avoid overflow
        //Corner case: x == 0
        if(x == 0) {
            return 0;
        }
        long begin = 1, end = (long)x - 1, mid;
        
        while(begin < end - 1) {
            mid = begin + (end - begin) / 2;
            
            if(mid * mid == x) {
                return (int)mid;
            } else if(mid * mid < x) {
                begin = mid;
            } else { //mid * mid > x
                end = mid;   
            }
        }
        
        // begin == end - 1 || begin = end - 1 (x == 1) || begin == end (x == 2)
        if(begin * begin == x || end * end > x) {
            return (int)begin;
        }
        return (int)end;
    }
}

69. Sqrt(x) (#2 Binary search).java

// Binary search solution: divide x by mid and compare the quotient with mid
// Time: O(logx), 1ms
// Space: O(1), 33.7mb
class Solution {
    public int mySqrt(int x) {
        // Corner cases
        if(x == 0 || x == 1) return x;
        
        int begin = 0, end = x;
        while(begin <= end) {
            int mid = begin + (end - begin) / 2;
            int sqrt = x / mid; // Equivalent to target
            
            if(sqrt == mid) {
                return sqrt;
            } else if(sqrt < mid) { // mid is too large, move to the left range
                end = mid - 1;
            } else {
                begin = mid + 1;
            }
            
        }
        
        // begin + 1 == end. sqrt is somewhere between (end, begin), we return the end to do truncating
        return end;
    }
}