โปรแกรมตรวจสอบ Perfect Square โดยไม่ใช้ sqrt ใน Python

ตรวจสอบว่า n เป็น Perfect Square (มีจำนวนเต็ม a ที่ a*a=n) โดยไม่ใช้ sqrt()

ตัวอย่าง: n=121 → True (11×11)

ขั้นตอน (Binary Search)

1. n==0 หรือ 1: True
2. start=2, stop=n//2
3. Binary Search หา k ที่ k*k == n

ตัวอย่างโค้ด

def solve(n):
    if n == 0 or n == 1:
        return True
    start = 2
    stop = n // 2
    while start <= stop:
        temp = range(start, stop + 1)
        k = temp[len(temp) // 2]
        k_squared = k * k
        if k_squared == n:
            return True
        if k_squared > n:
            start = temp[0]
            stop = k - 1
        else:
            start = k + 1
            stop = temp[-1]
    return False

n = 121
print(solve(n))  # Output: True

อินพุต

121

เอาต์พุต

True