পাইথনে সর্টেড অ্যারে থেকে অনুপস্থিত উপাদান বের করা

ধরা যাক একটি অ্যারে A আছে যেখানে nটি ইউনিক নম্বর রয়েছে অ্যাসেন্ডিং অর্ডারে, কিন্তু একটি উপাদান অনুপস্থিত। আমাদের সেই অনুপস্থিত উপাদানটি বের করতে হবে।

যেমন, A = [1, 2, 3, 4, 5, 6, 7, 9] হলে আউটপুট হবে 8।

সমাধানের ধাপসমূহ (বাইনারি সার্চ)

n := A-এর আকার, left := 0, right := n-1
while right > left:
- mid := left + (right - left) // 2
- যদি A[mid] - mid == A[0] হয়:
  - যদি A[mid+1] - A[mid] > 1 হয়: return A[mid] + 1
  - অন্যথায়: left := mid + 1
- অন্যথায়:
  - যদি A[mid] - A[mid-1] > 1 হয়: return A[mid] - 1
  - অন্যথায়: right := mid - 1
return -1

উদাহরণ

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

ইনপুট

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