สมมติว่าเรามีตัวเลข x และ x เป็นจำนวนไม่ติดลบ เราต้องหารากที่สองของ x โดยไม่ใช้ฟังก์ชันไลบรารีใดๆ เราต้องสร้างฟังก์ชันของตัวเองเพื่อประเมิน sqrt(x) ในฟังก์ชันนี้ ตัวเลขทศนิยมของผลลัพธ์จะถูกตัดทิ้ง
สมมติค่าของ x เป็น 4 ผลลัพธ์จะเป็น 2 ถ้า x เป็น 8 ผลลัพธ์ก็จะเป็น 2 เพราะ sqrt(8) คือ 2.82842 แต่เราจะเอาเฉพาะส่วนจำนวนเต็ม
วิธีการแก้ปัญหา
- เริ่มต้น l = 1, และ h = x + 1, answer = 0
- while h > l:
- mid = (h + l) / 2
- ถ้า mid * mid <= x ให้ l := mid + 1, answer = mid
- มิฉะนั้น h = mid
- คืนค่า answer
ตัวอย่าง (Python)
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
low = 1
high = x + 1
ans = 0
while high > low:
mid = (high + low) // 2
print(low, mid, high)
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))
อินพุต
print(ob1.mySqrt(4)) print(ob1.mySqrt(16)) print(ob1.mySqrt(7)) print(ob1.mySqrt(15))
เอาต์พุต
2 4 2 3
