Implement Integer Square Root

Given a non-negative integer x, implement sqrt(x) and return the integer part of its square root, i.e., floor(sqrt(x)).

Requirements:

• Do not use a built-in square root function or exponent operator.
• Your solution should handle large 32-bit signed integers without overflow.
• Explain the time and space complexity.

Examples:

• x = 4 returns 2.
• x = 8 returns 2, because sqrt(8) = 2.828... and the integer part is 2.

Expected approach:

• First solve it using binary search.
• Follow-up: discuss whether there is a more efficient practical method, such as Newton's method, and compare it with binary search.

Implement Integer Square Root

Given a non-negative integer x, implement integer square root and return the integer part of its square root, i.e., floor(sqrt(x)).

Requirements:

• Do NOT use any built-in square root function or the exponent/power operator.
• Handle large 32-bit signed integers without overflow (be careful with mid * mid).
• Explain the time and space complexity.

Examples:

• x = 4 returns 2.
• x = 8 returns 2, because sqrt(8) = 2.828... and the integer part is 2.
• x = 0 returns 0; x = 1 returns 1.

Approach: Use binary search over the candidate answer range [0, x] (you can tighten the high bound to x // 2 for x >= 2). For each mid, compare mid * mid against x. Follow-up: Newton's method converges faster in practice (quadratically) than binary search's logarithmic step count — worth discussing the trade-off.

Constraints

• 0 <= x <= 2147483647 (fits in a 32-bit signed integer)
• Do not use any built-in square root function or exponent/power operator
• Must not overflow: in Java/C++, compute mid * mid using a 64-bit type

Hints

1. The answer lies in the range [0, x]. For x >= 2, the square root is at most x // 2, so you can search [1, x // 2].
2. Binary search on the candidate answer: if mid * mid <= x, mid could be the answer (record it) and search higher; otherwise search lower.
3. In languages with fixed-width integers, mid * mid can overflow 32 bits — cast to a 64-bit (long / long long) before multiplying.
4. Follow-up: Newton's iteration r = (r + x // r) // 2 converges quadratically and is the more efficient practical method.