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 i^{2} < N, and whenever i^{2} >= N return i.

for( int i = 1; i <= N/2 ; i++ )

{

if( i*i >= N )

return i;

}

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 mid^{2} <= N and (mid+1)^{2} >N. If this is satisfied, we return mid.

If mid^{2} > 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.