The Square Root Estimator: Compute x Using Binary Search

In the engineering workshops of Prime City, the Royal Architect needs to compute square roots without floating-point hardware. Using binary search on integers, the Architect can find the integer square root of any non-negative number. "The integer square root of x is the largest integer r such that r^2 <= x," the Architect explains. "Binary search between 0 and x: if mid^2 <= x, the answer is at least mid, so search right. Otherwise, search left." Given a non-negative integer x, compute its integer square root (the largest integer r such that r^2 <= x). Constraints: 0 <= x <= 10^18 Input: 16 Output: 4 Input: 8 Output: 2