Given a non-negative integer x, compute and return the square root of x rounded down to the nearest integer. The result must also be non-negative.

Built-in exponent functions or operators (e.g., pow(x, 0.5) in C++ or x ** 0.5 in Python) are not permitted.

Constraints:

• $0 \leq$ x $\leq 2^{31} - 1$

The key insight is that the integer square root of x lies somewhere in the range $[1, x/2]$ for any x $\geq$ $2$, and this range is sorted, making it a perfect candidate for Modified Binary Search. Instead of scanning every candidate linearly, we ...