For example int_sqrt(4) = 2, int_sqrt(10) = 3. (We have to take floor of the actual square root)
A simple method is to iterate i from 1 to N/2 and keep checking until i2 < N, and whenever i2 >= N return i.
for( int i = 1; i <= N/2 ; i++ )
if( i*i >= N )
But this algorithm takes O(n) time. For large numbers this takes a lot of time. Any way to improve this further?
Binary search comes to our rescue. we start with the initial range [0, N]. In each iteration we check if mid2 <= N and (mid+1)2 >N. If this is satisfied, we return mid.
If mid2 > N, we confine our search to the left half; otherwise we search in the right half.
This implementation takes only O(log N) time.
Here is the C++ implementation.