69. Sqrt(x)

a·a is monotonically increasing in a, which is the signal to binary-search the answer — not over an array, but over the value range [0, x], looking for the largest a with a·a ≤ x. Each step, if…