Finding the integer square root of a number

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² < N, and whenever i² >= 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² <= N and (mid+1)² >N. If this is satisfied, we return mid.

If mid² > 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.