Đoán căn bậc hai nguyên gần nhất trong Python

Cho số không âm n, tìm số r sao cho r * r = n và làm tròn xuống đến số nguyên gần nhất. Không dùng hàm căn bậc hai có sẵn.

Ví dụ, 1025 -> 32.

Các bước giải quyết (tìm kiếm nhị phân):

• Nếu n <= 1, trả về n.
• start := 1, end := n.
• Trong khi start < end:
  • mid = (start + end) >> 1 (chia 2).
  • Nếu mid * mid <= n: start = mid + 1.
  • Ngược lại: end = mid.
• Trả về start - 1.

Ví dụ minh họa

class Solution:
    def solve(self, n):
        if n <= 1:
            return n
        start, end = 1, n
        while start < end:
            mid = (start + end) >> 1
            if mid * mid <= n:
                start = mid + 1
            else:
                end = mid
        return start - 1

ob = Solution()
print(ob.solve(1025))

Đầu vào

1025

Đầu ra

32