मान लीजिए हमारे पास एक सरणी है, जो शुरू में बढ़ती है फिर घटती है। हमें सरणी में अधिकतम मान ढूंढना है। इसलिए यदि सरणी तत्व A = [8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1] की तरह हैं, तो आउटपुट 450 होगा।
हम इसे हल करने के लिए बाइनरी सर्च का उपयोग कर सकते हैं। तीन शर्तें हैं:
- जब मध्य अपने दोनों आसन्न तत्वों से बड़ा होता है, तो मध्य अधिकतम है
- यदि मध्य अगले तत्व से बड़ा है, लेकिन पिछले तत्व से छोटा है, तो अधिकतम मध्य के बाईं ओर है।
- यदि मध्य तत्व अगले तत्व से छोटा है, लेकिन पिछले तत्व से बड़ा है, तो अधिकतम मध्य के दाईं ओर है।
उदाहरण
#include<iostream> using namespace std; int getMaxElement(int array[], int left, int right) { if (left == right) return array[left]; if ((right == left + 1) && array[left] >= array[right]) return array[left]; if ((right == left + 1) && array[left] < array[right]) return array[right]; int mid = (left + right)/2; if ( array[mid] > array[mid + 1] && array[mid] > array[mid - 1]) return array[mid]; if (array[mid] > array[mid + 1] && array[mid] < array[mid - 1]) return getMaxElement(array, left, mid-1); else return getMaxElement(array, mid + 1, right); } int main() { int array[] = {8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1}; int n = sizeof(array)/sizeof(array[0]); cout << "The maximum element is: " << getMaxElement(array, 0, n-1); } आउटपुट
The maximum element is: 450
