One of the tricks to designing algorithms is to reuse strategies from similar problems. The following question concerns an application of binary search to a different problem. The reason we can use binary search is because the problem can be thought of as searching an ordered array of integers, even though we dont actually implement the array.

The integer square root of an integer n is defined to be the integer m such that m2 n < (m + 1)2 .

Use a binary search strategy to write a function to find the integer square root.