โปรแกรมหาพจน์ที่หายไปจาก Arithmetic Sequence ใน Python

ให้ Array nums ขนาด n-1 เป็น Arithmetic Sequence ขาด 1 พจน์ (ไม่ใช่พจน์แรก/สุดท้าย) หาพจน์ที่หาย

ตัวอย่าง: nums=[5,7,11,13] → 9 (สูตร 2i+5, i=2 → 9)

ขั้นตอน (Binary Search)

1. ถ้า len==2: คืนค่าเฉลี่ย
2. ถ้า nums[0]==nums[1]: คืน nums[0]
3. interval = (last-first)//len
4. Binary Search หาจุดที่ nums[mid] != first + interval*mid

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

def solve(nums):
    if len(nums) == 2:
        return sum(nums) // 2
    if nums[0] == nums[1]:
        return nums[0]
    lower = nums[0]
    upper = nums[-1]
    interval = (upper - lower) // len(nums)
    pointer = len(nums) // 2
    left = 0
    right = len(nums) - 1
    while left != right:
        if nums[pointer] != nums[0] + interval * pointer:
            if nums[pointer - 1] == nums[0] + interval * (pointer - 1):
                return nums[0] + interval * pointer
            else:
                right = pointer
                pointer = (left + right) // 2
        else:
            if right - left == 1:
                pointer = right
            else:
                left = pointer
                pointer = (left + right) // 2

nums = [5, 7, 11, 13]
print(solve(nums))  # Output: 9

อินพุต

[5, 7, 11, 13]

เอาต์พุต

9