Leetcode: Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Understand the problem:
The problem asks for implementing the sqrt(x). Note that the input and return value are integer types. For the mathematical related questions, we should naturally think of using binary search ideas. 

Solution:
The square root of an integer n is within [1, n/2 + 1]. Thus we can binary search from 1 to n/2 + 1. If the square root of the middle is less than n, the target must be in the left part. Else it must be in the right part.

Code (Java):

public class Solution {
    public int sqrt(int x) {
        if (x == 0) {
            return 0;
        }
        
        if (x < 0) {
            return -1;
        }
        
        long lo = 0;
        long hi = x / 2 + 1;
        
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            long sq = mid * mid;
            if (sq == x) {
                return (int) mid;
            }
            
            if (sq < x) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        
        return (int) hi;
    }
}