Pattern Recognition Drill
Easy Binary Search
The Problem
Compute floor(sqrt(x)) without using math.sqrt.
What approach would you use?
Think about it before scrolling down.
Binary search on [0, x]. If mid² <= x, answer is at least mid (search right). O(log x).
Common Trap
This is 'binary search on the answer' — a crucial pattern. The sorted array is implicit.