Square Root Binary Search Java | Fresher Interview
Fast recall
Quick revision
Core answer
mid*mid == n return mid; if mid*mid < n record mid and go right (left = mid + 1); else go left (right = mid - 1). Return the last mid whose square was <= n (the floor). Cast mid*mid to long to avoid overflow. Time is O(log n).Whether you recognize this as binary search on a monotonic answer space rather than reaching for Math.sqrt()
Calling Math.sqrt() (defeats the question) or computing mid*mid as int and overflowing for large n
Say explicitly 'I'm searching the answer space 1..n' and guard the multiplication with a long cast
Interview-ready guide
Interview answer
I'd solve this with binary search on the answer space from one to n, and I'd say that out loud, because the insight is that I'm not searching an array, I'm searching the range of possible answers.
The possible square roots form a sorted sequence, and for any candidate I can decide whether it's too small, too big, or exactly right, which is all binary search needs. I set low to one and high to n. Each step I take the midpoint and compare mid times mid with n.
If they're equal, mid is the exact square root and I return it. If mid times mid is less than n, then mid might be my answer, so I store it as a candidate and move low up to mid plus one to try larger values. If mid times mid is greater than n, mid is too big, so I move high down to mid minus one.
When the loop ends, my stored candidate is the floor of the square root, the largest integer whose square doesn't exceed n. Two traps I'm careful about. First, I cast mid times mid to a long before comparing, because for large n that multiplication overflows a regular int and gives a wrong, even negative, result.
Second, I return the stored candidate, not low, because when the loop exits low has gone one past the floor. The whole thing is O of log n time and constant space. And the bigger point I'd make is that this same answer-space technique solves a whole family of problems, anything where I'm optimizing a value and can check a candidate efficiently.
Square Root Binary Search Java | Fresher Interview
Direct Answer
Binary search the answer space from 1 to n. For the integer square root: if mid*mid == n return mid; if mid*mid < n record mid and go right (left = mid + 1); else go left (right = mid - 1). Return the last mid whose square was <= n (the floor). Cast mid*mid to long to avoid overflow. Time is O(log n).
Deep Dive & Architecture
Binary search works because the possible answers have a clean boundary. For a non-negative number n, candidates whose square is at most n are valid; after one point, every larger candidate is invalid. The task is to find the last valid candidate.
Worked example: n = 17
Search from 1 to 17. Candidate 9 gives 81, so everything from 9 upward is too large. Candidate 4 gives 16, so remember 4 and try larger values. Candidate 6 gives 36 and candidate 5 gives 25, so both are too large. The range closes and the remembered value 4 is returned. This is the floor because 4² <= 17 but 5² > 17.
The cases 0 and 1 can return immediately. For larger inputs, calculate the midpoint as low + (high - low) / 2. Cast before multiplication—(long) mid * mid—because an int product can overflow before it is assigned. An alternative is comparing mid <= n / mid, provided division by zero is avoided.
Only one half of the candidate range remains after each comparison, giving O(log n) time and O(1) extra space.
Code Example
int mySqrt(int n) {
if (n < 2) return n;
int lo = 1, hi = n, ans = 0;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
long sq = (long) mid * mid; // long cast avoids overflow
if (sq == n) return mid;
else if (sq < n) { ans = mid; lo = mid + 1; } // candidate, go bigger
else hi = mid - 1; // too big, go smaller
}
return ans; // floor of sqrt(n)
}
// n = 17: lo=1,hi=17
// mid=9 -> 81>17 -> hi=8; mid=4 -> 16<17 -> ans=4,lo=5
// mid=6 -> 36>17 -> hi=5; mid=5 -> 25>17 -> hi=4 -> stop, return 4
Common Mistakes & Pitfalls
- Using
Math.sqrt()in an algorithm exercise: it skips the boundary-search logic the question is asking you to implement. intoverflow:mid * midoverflows for largen; cast one operand tolong.- Returning
loinstead ofans: at exitlois one past the floor; return the storedans(orhi). - Skipping
n < 2: 0 and 1 are their own square roots.
Check your understanding
Answer these without looking back at the article.
- How does binary search work and what is its time complexity?
- Why do you use mid = left + (right - left) / 2 instead of (left + right) / 2 in binary search?
- Can binary search be applied to problems other than searching in sorted arrays?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.