integer square root algorithm an efficient method to calculate the square root of a nonnegative integer num rounded down to the nearest integer it uses a binary search approach to find the integer square root without using any builtin exponent functions or operators https en wikipedia orgwikiintegersquareroot https docs python org3librarymath htmlmath isqrt note this algorithm is designed for nonnegative integers only the result is rounded down to the nearest integer the algorithm has a time complexity of ologx original algorithm idea based on binary search returns the integer square root of a nonnegative integer num args num a nonnegative integer returns the integer square root of num raises valueerror if num is not an integer or is negative integersquarerooti for i in range18 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 integersquareroot625 25 integersquareroot2147483647 46340 from math import isqrt allintegersquarerooti isqrti for i in range20 true integersquareroot1 traceback most recent call last valueerror num must be nonnegative integer integersquareroot1 5 traceback most recent call last valueerror num must be nonnegative integer integersquareroot0 traceback most recent call last valueerror num must be nonnegative integer returns the integer square root of a non negative integer num args num a non negative integer returns the integer square root of num raises valueerror if num is not an integer or is negative integer_square_root i for i in range 18 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 integer_square_root 625 25 integer_square_root 2_147_483_647 46340 from math import isqrt all integer_square_root i isqrt i for i in range 20 true integer_square_root 1 traceback most recent call last valueerror num must be non negative integer integer_square_root 1 5 traceback most recent call last valueerror num must be non negative integer integer_square_root 0 traceback most recent call last valueerror num must be non negative integer
def integer_square_root(num: int) -> int:
    
    if not isinstance(num, int) or num < 0:
        raise ValueError("num must be non-negative integer")

    if num < 2:
        return num

    left_bound = 0
    right_bound = num // 2

    while left_bound <= right_bound:
        mid = left_bound + (right_bound - left_bound) // 2
        mid_squared = mid * mid
        if mid_squared == num:
            return mid

        if mid_squared < num:
            left_bound = mid + 1
        else:
            right_bound = mid - 1

    return right_bound


if __name__ == "__main__":
    import doctest

    doctest.testmod()