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.

Why this is worth learning

The predicate mid²<=x changes from true to false over nonnegative mid. Find its last true value, retaining a feasible answer while narrowing the remaining search.

Before coding: one-minute experiment

For x=15, why is 3 the answer even though 4 is closer to the real square root? Which two inequalities certify it?

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)

Trying integer candidates from zero until the next square is too large gives a correct O(sqrt(x)) baseline. The predicate m²<=x is true on an initial interval of nonnegative integers, then false forever. Binary search can find its last true value, provided the multiplication used by the predicate is itself representable. The result needs a floor certificate, not closeness to a floating-point approximation.

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

Invariant: ans is feasible (ans²<=x), and every feasible value larger than ans remains in [lo,hi]. The final answer may already be saved in ans and lie outside the active interval.

Algorithm (step-by-step)

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

Correctness sketch

Maintain ans as a tested value with ans²<=x and an interval containing any larger feasible candidate. If mid²<=x, midpoint is feasible and every smaller index is no better; record mid and search above it. Otherwise every value at least mid is infeasible, so search below. The interval strictly shrinks. When exhausted, ans is feasible and no larger candidate is feasible, so ans²<=x<(ans+1)². Multiplication is performed in int64; with x<=2^31-1, even the largest tested midpoint squared fits signed 64-bit.

Trace (hand walkthrough)

For x=8, follow the inclusive interval and retain a separate feasible answer.

lo	hi	mid	mid²	ans after step	Next interval
0	8	4	16	0	[0,3]
0	3	1	1	1	[2,3]
2	3	2	4	2	[3,3]
3	3	3	9	2	[3,2], empty

Return saved ans=2. For x=16 the midpoints are 8,3,5,4; the last step records ans=4 and exhausts the interval. Both traces certify ans²<=x<(ans+1)².

Pitfalls to avoid

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

Debugging lens

Test perfect squares and their immediate neighbors, including the upper signed-32-bit boundary. A floating approximation without integer correction can misclassify a boundary.

Complexity

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

Implementation notes (Go)

• Use int64 for mid*mid to avoid overflow.

Reconstruction checkpoint

For x=15, why is 3 the answer even though 4 is closer to the real square root? Which two inequalities certify it?

Model answer

The operation is floor, not nearest integer: 3²=9<=15 and 4²=16>15. These inequalities certify the exact integer square root.

Return to Math · Module quiz