Căn bậc hai (Sqrt(x)) trong Python

Cho số không âm x. Tính căn bậc hai nguyên (phần nguyên). Ví dụ: 4→2, 8→2 (vì sqrt(8)=2.828).

Giải pháp

Tìm kiếm nhị phân:

• low=1, high=x+1, ans=0.
• Trong khi high>low: mid=(high+low)//2. Nếu mid*mid<=x: low=mid+1, ans=mid; else high=mid.
• Trả về ans.

Ví dụ

Triển khai Python:

class Solution(object): 
    def mySqrt(self, x): 
        low = 1 
        high = x+1 
        ans = 0 
        while high>low: 
            mid = (high+low)//2 
            if mid*mid<=x: 
                low = mid+1 
                ans = mid 
            else: 
                high = mid 
        return ans 
ob1 = Solution() 
print(ob1.mySqrt(4)) 
print(ob1.mySqrt(16)) 
print(ob1.mySqrt(7)) 
print(ob1.mySqrt(15))

Đầu vào

print(ob1.mySqrt(4)) print(ob1.mySqrt(16)) print(ob1.mySqrt(7)) print(ob1.mySqrt(15))

Đầu ra

2 4 2 3