Sqrt(x)

Return the integer square root of a non-negative integer x (floor of sqrt). Direct floating-point sqrt is unnecessary and can introduce rounding issues.

Function signature

func MySqrt(x int) int

Inputs / outputs

• x: non-negative integer.
• Return: floor(sqrt(x)).

Example

8 -> 2 (since sqrt(8) ~ 2.828)
16 -> 4

Constraints

• 0 <= x <= 2^31 - 1

Core idea (near-solution)

Binary search for the largest integer m such that m*m <= x.

Invariant: the answer always lies within the current search interval.

Algorithm (step-by-step)

1. Set lo=0, hi=x, ans=0.
2. While lo <= hi:
   • mid = (lo+hi)/2.
   • If mid*mid <= x, set ans=mid, move lo=mid+1.
   • Else move hi=mid-1.
3. Return ans.

Correctness sketch

• Invariant: the answer always lies within the current search interval.
• The formula/transform follows from number properties or monotonicity.
• Each iteration preserves the mathematical invariant.
• Thus the computed value matches the definition of the problem.

Trace (hand walkthrough)

Example input:
8 -> 2 (since sqrt(8) ~ 2.828)
16 -> 4

Walk:
- x=8: mid=4 (too big) -> hi=3; mid=2 (ok) -> lo=3; mid=3 (too big) -> answer 2
- x=16: mid=4 -> exact 4

Pitfalls to avoid

• Integer overflow when computing mid*mid.
• Off-by-one in the bounds.

Complexity

• Time: O(log x).
• Extra space: O(1).

Implementation notes (Go)

• Use int64 for mid*mid to avoid overflow.