66. Sqrt(x)

The floor of the square root lies in [1, x/2]. Binary search that range: for a middle guess, compare its square to x and discard half the candidates each step.

Idea

The answer is the largest integer r with r*r <= x. Since r*r grows monotonically, we can binary search for it. For x >= 2 the root is at most x/2, bounding the search range.

Algorithm

1. If x < 2, return x (0→0, 1→1).
2. lo = 1, hi = x // 2. While lo <= hi:
   • mid = (lo + hi) // 2, sq = mid*mid.
   • If sq == x, return mid.
   • If sq < x, search right (lo = mid + 1).
   • Else search left (hi = mid - 1).
3. When the loop ends, hi is the floor of the square root.

Worked example: x = 8

• lo=1, hi=4, mid=2 → 4 < 8 → lo=3. mid=3 → 9 > 8 → hi=2. lo(3) > hi(2), stop.
• Return hi = 2 (since 2² = 4 ≤ 8 < 9 = 3²).

Complexity

• Time: O(log x).
• Space: O(1).

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