Well, I think one should be able to come up with a way of doing so on the fly just from knowing that the square root function is monotonically increasing, and k

Well, I think one should be able to come up with a way of doing so on the fly just from knowing that the square root function is monotonically increasing, and knowing binary search? Of course, doing it another way might be more efficient.