Sqrt(x)
Given a non-negative integer x, return the integer part of its square root — the largest integer k such that k * k <= x.
Intuition
You are searching for the largest k where k² <= x. Since the candidates 0, 1, 2, …, x are in sorted order, and k² is monotonically increasing, binary search fits perfectly. Pick a midpoint, square it, and decide which half to keep. The answer is the rightmost mid whose square does not exceed x.
Any time you need to find the boundary value of a monotonic function — 'the largest k such that f(k) <= target' — binary search on the answer is the tool. Here f(k) = k², but the same template works for cube roots, finding a threshold in a sorted array, or minimising a cost function that is convex.
Approach
Set up binary search over `[0, x]`
The answer lies between 0 and x (since sqrt(x) <= x for all x >= 1, and sqrt(0) = 0). Initialize left = 0 and right = x. We will narrow this range until we land on the exact integer square root.
Compare `mid * mid` against `x` and keep the right half
Compute mid = (left + right) // 2. If mid mid <= x, then mid is a candidate — record it and search higher (left = mid + 1). If mid mid > x, then mid is too large — search lower (right = mid - 1). The last candidate recorded is the answer.
Return the stored answer
When the loop ends (left > right), the stored answer is the largest mid satisfying mid² <= x. Time is O(log x) because the range halves each iteration. Space is O(1).
Solution
Common pitfalls
Using mid * mid == x as the only success condition
if mid * mid == x:
return midif mid * mid <= x:
ans = mid
left = mid + 1You need the floor of the square root, not an exact match. For non-perfect squares like x = 8, no mid satisfies mid² == 8, and the function would return nothing. Recording every mid where mid² <= x and continuing the search finds the correct floor.
Setting right = x // 2 to optimise the range
right = x // 2
right = x
For x = 1, x // 2 = 0, and the answer 1 is outside the range. The saving is negligible (one fewer iteration of log x) and breaks the smallest input.
Integer overflow when computing mid * mid in typed languages
int sq = mid * mid;
long sq = (long) mid * mid;
In Java/C++, mid can be up to ~46340 before mid mid overflows a 32-bit int. For x near INT_MAX, mid is around 46340, and mid mid exceeds 2^31. Python has arbitrary-precision ints so this doesn't apply there, but the C++ and Java solutions must use long.
Edge cases
x = 0The range is [0, 0]. mid = 0, 0 * 0 = 0 <= 0, so the answer is 0.
x = 1mid = 0 first, then left = 1, mid = 1, 1 <= 1, answer is 1.
x = 16mid = 4 gives 16 <= 16, so the answer is exactly 4. No truncation.