পাইথনে প্রদত্ত বিটোনিক সিকোয়েন্সে বিটোনিক পয়েন্ট খুঁজুন

ধরুন আমাদের একটি বাইটোনিক সিকোয়েন্স আছে, এতে আমাদের বাইটোনিক পয়েন্ট খুঁজে বের করতে হবে। আমরা জানি একটি Bitonic ক্রম হল সংখ্যার একটি ক্রম যা প্রথমে কঠোরভাবে বৃদ্ধি পায় তারপর একটি নির্দিষ্ট বিন্দুর পরে এটি কঠোরভাবে হ্রাস পায়। এই বিন্দুটি বাইটোনিক পয়েন্ট। শুধুমাত্র ক্রমবর্ধমান বা শুধুমাত্র হ্রাসের জন্য, বিটোনিক পয়েন্ট উপলব্ধ নয়৷

সুতরাং, যদি ইনপুটটি [7, 8, 9, 12, 10, 6, 3, 2] এর মত হয়, তাহলে আউটপুট হবে 12

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

• একটি ফাংশন সংজ্ঞায়িত করুন binary_search(array, l, r)
• যদি l <=r হয়, তাহলে −
  • m :=(l + r) / /2
• যদি অ্যারে[m - 1] array[m + 1], তাহলে −
  • রিটার্ন m
• যদি array[m]
• বাইনারি_সার্চ (অ্যারে, m + 1, r) ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def binary_search(array, l, r):
   if (l <= r):
      m = (l + r) // 2;
      if (array[m - 1] < array[m] and array[m] > array[m + 1]):
         return m;
      if (array[m] < array[m + 1]):
         return binary_search(array, m + 1,r);
      else:
         return binary_search(array, l, m - 1);
   return -1;
array = [7, 8, 9, 12, 10, 6, 3, 2]
n = len(array);
index = binary_search(array, 1, n-2);
if (index != -1):
   print(array[index]);

ইনপুট

[7, 8, 9, 12, 10, 6, 3, 2]

আউটপুট

12