Sqrt(x)
An easy Binary Search interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Binary Search
- Sheets
- 3
- Core for
- 7 roles
The problem
Given a non-negative integer x, compute and return the square root of x truncated toward zero. Do not use any built-in exponent function or operator.
Example 1
- Input
- x = 4
- Output
- 2
- Why
- The square root of 4 is 2, so we return 2.
Example 2
- Input
- x = 8
- Output
- 2
- Why
- The square root of 8 is approximately 2.828, which truncates to 2.
Constraints
- 0 <= x <= 2^31 - 1
How to think about it
Updated 2026-09-29The sequence of squared integers is strictly monotonic. Finding the integer square root is asking for the largest integer whose square does not exceed x, turning what looks like arithmetic evaluation into a standard monotonic predicate search.
Approaches, worst first
Linear increment
time O(sqrt(x)) · space O(1)
Test integers starting from 1 upward until the square surpasses x. It tests every candidate value one by one, resulting in unacceptable runtimes for large inputs.
Binary search on integer rangeWrite this one
time O(log x) · space O(1)
Search over the range from 0 to x. If mid * mid <= x, record mid as a viable floor answer and search higher; otherwise search lower.
Where people lose marks · 3
- Computing mid * mid directly in 32-bit signed integers overflows when mid approaches 2^16; use 64-bit integers or rewrite the comparison as mid <= x / mid.
- Dividing by mid when mid is zero causes division-by-zero crashes on input x = 0; handle 0 as an explicit early return or bound the search between 1 and x.
- Failing to store the best valid candidate during truncation leads to returning an overshot value when the loop finishes.
The theory behind it
Binary Search — the ground this problem stands on. All Binary Search problems
What Binary Search is
Binary search is the guessing strategy used when searching a thick telephone directory or guessing a secret number between one and a hundred. Rather than inspecting names one by one from the first page, the search opens straight to the middle page. If the target precedes that middle entry, the entire back half is discarded; if it follows, the front half is eliminated. Repeating this halved split finds the item with remarkable speed.
When to reach for it
Reach for binary search when queries target sorted collections, rotated sorted arrays, or monotonic answer spaces. Strong hints include logarithmic time constraints like O(log n) or search ranges exceeding one billion where stepping one value at a time times out. It also applies when validating whether a guessed solution is possible via a monotonic boolean check, known as binary search on answer.
How the pattern works
Define the search territory with two inclusive pointers, low and high. Compute the midpoint using low plus half the difference to high, avoiding integer overflow. Formulate an exact boolean condition that divides the range into true and false halves. Decide whether the boundary condition includes the midpoint or shifts strictly past it. The loop invariant states that the sought target, if it exists, remains trapped inside the interval throughout every iteration.
More Binary Search problems
Target Roles
Core requirement for 7 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .