Tìm phần tử thiếu trong mảng đã sắp xếp các số liên tiếp trong Python

Cho mảng A gồm n số duy nhất, sắp xếp tăng dần nhưng thiếu một phần tử. Tìm phần tử thiếu đó.

Ví dụ: A = [1, 2, 3, 4, 5, 6, 7, 9] → Kết quả: 8.

Thuật toán (Binary Search)

1. Khởi tạo left = 0, right = n-1.
2. Trong khi right > left:
   • mid = left + (right - left) // 2.
   • Nếu A[mid] - mid == A[0]: phần tử thiếu ở bên phải. Kiểm tra A[mid+1] - A[mid] > 1 thì trả về A[mid]+1, ngược lại left = mid + 1.
   • Ngược lại: phần tử thiếu ở bên trái. Kiểm tra A[mid] - A[mid-1] > 1 thì trả về A[mid]-1, ngược lại right = mid - 1.
3. Trả về -1 nếu không tìm thấy.

Ví dụ code

def search_missing_item(A):
    n = len(A)
    left, right = 0, n - 1
    mid = 0
    while right > left:
        mid = left + (right - left) // 2
        if A[mid] - mid == A[0]:
            if A[mid + 1] - A[mid] > 1:
                return A[mid] + 1
            else:
                left = mid + 1
        else:
            if A[mid] - A[mid - 1] > 1:
                return A[mid] - 1
            else:
                right = mid - 1
    return -1

A = [1, 2, 3, 4, 5, 6, 7, 9]
print(search_missing_item(A))

Input

[1, 2, 3, 4, 5, 6, 7, 9]

Output

8