visual walkthrough
Sqrt(x)
Searching over the answer space instead of an array.
The idea
There's no array here, but the answers 0, 1, 2, …, x are "sorted": k² ≤ x is true for small k and false after some point.
Binary search over those answers for the last k that fits.
Complexity
| approach | time | space |
|---|---|---|
| Count up | O(√x) | O(1) |
| Binary search on the answer | O(log x) | O(1) |