Easy · Answer-Space Binary Search
Understand → Visualise → Practice.
Return the floor of the square root of non-negative n without using a square-root function.
The answer is the largest m with m × m ≤ n. Squares grow with m, so binary search the range 0..n for that boundary.
lo = 0, hi = n.
If mid × mid ≤ n, mid is possible: record it and search higher; otherwise search lower.
The last recorded mid is ⌊√n⌋.
O(log n) time and O(1) space.
In fixed-width languages mid × mid can overflow; compare mid ≤ n / mid instead.
Read the full guides first: Sorting Algorithms and Their Trade-offs, Binary Search and Boundary Finding.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.