পাইথনে পরপর সংখ্যার একটি সাজানো অ্যারেতে অনুপস্থিত উপাদান খুঁজুন

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

সুতরাং, যদি ইনপুটটি A =[1, 2, 3, 4, 5, 6, 7, 9] এর মত হয়, তাহলে আউটপুট হবে 8।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=A

  এর আকার

• বাম :=0

• ডান :=n - 1

• মধ্য :=0

• যখন ডান> বাম, করুন

  • মধ্য :=বাম +(ডান - বাম) / 2

  • যদি A[মিড] - মিড A[0] এর মত হয়, তাহলে

    • যদি A[মধ্য + 1] - A[মধ্য]> 1 হয়, তাহলে

      • A[মিড] + 1

        ফেরত দিন

    • অন্যথায়,

      • বাম :=মধ্য + 1

  • অন্যথায়,

    • যদি A[মধ্য] - A[মধ্য - 1]> 1 হয়, তাহলে

      • ফেরত A[মধ্য] - 1

    • অন্যথায়,

      • ডান:=মধ্য - 1

• রিটার্ন -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]

আউটপুট

8