Chương trình tìm số bị thiếu trong cấp số cộng trong Python

Cho mảng nums chứa n-1 số của một cấp số cộng (mất đi một số không phải đầu/cuối). Tìm số bị thiếu.

Ví dụ: nums = [5, 7, 11, 13] → kết quả 9 (công thức 2i+5, i=2 → 9).

Thuật toán giải quyết (Tìm kiếm nhị phân O(log n))

1. Nếu độ dài 2: trả về trung bình
2. Nếu hai phần tử đầu bằng nhau: cấp số cộng hằng → trả về giá trị đó
3. Tính interval = (last - first) // n (công sai)
4. Binary search trên mảng: so sánh nums[mid] với giá trị kỳ vọng first + interval*mid
5. Khi tìm thấy vị trí lệch: trả về giá trị kỳ vọng tại vị trí đó

Ví dụ minh họa

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))

Đầu vào

[5, 7, 11, 13]

Đầu ra

9