पायथन में दिए गए बिटोनिक अनुक्रम में बिटोनिक बिंदु खोजें

मान लीजिए हमारे पास एक बिटोनिक अनुक्रम है, हमें इसमें बिटोनिक पॉइंट ढूंढना है। जैसा कि हम जानते हैं कि बिटोनिक अनुक्रम संख्याओं का एक क्रम है जो पहले सख्ती से बढ़ रहा है फिर एक निश्चित बिंदु के बाद यह सख्ती से घट रहा है। यह बिंदु बिटोनिक बिंदु है। केवल बढ़ते या घटते क्रम के लिए, बिटोनिक बिंदु उपलब्ध नहीं हैं।

इसलिए, यदि इनपुट [7, 8, 9, 12, 10, 6, 3, 2] जैसा है, तो आउटपुट 12

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन को परिभाषित करें बाइनरी_सर्च(सरणी, एल, आर)
• यदि l <=r, तो −
  • एम :=(एल + आर) / /2
• अगर सरणी [एम ​​-1] <सरणी [एम] और सरणी [एम]> सरणी [एम ​​+ 1], तो -
  • वापसी एम
• अगर सरणी[m] <सरणी[m + 1], तो −
  • वापसी बाइनरी_सर्च (सरणी, एम + 1, आर)
• अन्यथा
  • रिटर्न बाइनरी_सर्च(सरणी, एल, एम -1)
• वापसी -1

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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