मान लीजिए हमारे पास एक बिटोनिक सीक्वेंस है, हमें इसमें बिटोनिक पॉइंट ढूंढना है। जैसा कि हम जानते हैं, एक बिटोनिक सीक्वेंस संख्याओं का एक क्रम है जो पहले सख्ती से बढ़ रहा है फिर एक निश्चित बिंदु के बाद सख्ती से घट रहा है। यह बिंदु बिटोनिक पॉइंट है। केवल बढ़ते या केवल घटते क्रम के लिए, बिटोनिक पॉइंट उपलब्ध नहीं हैं।
तो, यदि इनपुट [7, 8, 9, 12, 10, 6, 3, 2] जैसा है, तो आउटपुट 12 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
- binary_search(array, l, r) फंक्शन डिफाइन करें
- यदि l <= r, तो:
- m := (l + r) // 2
- यदि array[m - 1] < array[m] और array[m] > array[m + 1], तो:
- m लौटाएं
- यदि array[m] < array[m + 1], तो:
- binary_search(array, m + 1, r) लौटाएं
- अन्यथा
- binary_search(array, l, m - 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
