Problem #69: Sqrt(x)

Intuition & Strategy Breakdown

Use binary search on range [0, x]. Find the largest integer mid such that mid * mid <= x.

Python Solution

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        
        left, right = 2, x // 2
        
        while left <= right:
            mid = left + (right - left) // 2
            num = mid * mid
            if num > x:
                right = mid - 1
            elif num < x:
                left = mid + 1
            else:
                return mid
        
        return right

Java Solution

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