248. Integer Square Root
Print the largest integer r with r * r <= n. So for 10 the answer is 3,
because 3 squared is 9 and 4 squared is 16.
There is no array here, and it is still a binary search. The candidate answers
0, 1, 2, ... are in order, and r * r <= n is true for all of them up to a
point and false afterwards. Finding that boundary is the same halving you have
already written twice.
That is the shape worth taking away: binary search works on any ordered range of candidates where a condition flips once, not only on arrays.
Do not use a floating-point square root. At n near 10^18 a double has about
15 to 17 significant digits, so the result can be off by one, and the answer
either fails or needs a correction step anyway.
Constraints - `0 ≤ n ≤ 1000000000000000000`
Input
A single line containing one integer n.
Output
Print one integer, the largest r with r * r <= n.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.