O(n), linear search

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0

        for i in range(x+1):
            if i*i == x:
                return i
            elif i*i > x:
                return i-1

def main():
    s = Solution()

    print(s.mySqrt(4))
    print(s.mySqrt(8))
    print(s.mySqrt(1))

if __name__ == '__main__':
    main()
			

O(lg(n)), binary search

import math
class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0 or x == 1:
            return x

        l = 0
        r = x
        m = int((l+r))>>1

        while True:
            temp = m**2
            if temp == x:
                return m
            if temp < x and temp+(m<<1)+1 > x:
                return int(m)
            if temp > x:
                r = m
            else:
                l = m
            m = int((l+r))>>1

def main():
    s = Solution()

    print(s.mySqrt(4))
    print(s.mySqrt(8))
    print(s.mySqrt(1))
    print(s.mySqrt(16))
    print(s.mySqrt(26))
    print(s.mySqrt(2147395600), math.sqrt(2147395600)) # 46340

if __name__ == '__main__':
    main()