विवरण
अलग-अलग तत्वों का एक सॉर्टेड ऐरे दिया गया है जो किसी अज्ञात बिंदु पर रोटेटेड है, कार्य इसमें अधिकतम तत्व ढूंढना है।
उदाहरण
यदि इनपुट ऐरे {30, 40, 50, 10, 20} है तो अधिकतम तत्व 50 है।
एल्गोरिदम
- अधिकतम तत्व वह एकमात्र तत्व है जिसका अगला तत्व उससे छोटा है। यदि कोई अगला छोटा तत्व नहीं है, तो कोई रोटेशन नहीं है यानी अंतिम तत्व अधिकतम है
- हम इस शर्त की जांच मध्य तत्व के लिए करते हैं जिसकी तुलना हम mid - 1 और mid + 1 पर तत्वों से करते हैं। यदि अधिकतम तत्व mid - 1 और mid + 1 पर तत्वों के साथ नहीं है। यदि अधिकतम तत्व मध्य में नहीं है (न तो mid और न ही mid + 1), तो अधिकतम तत्व या तो बाएं आधे या दाएं आधे में स्थित है -
- यदि मध्य तत्व अंतिम तत्व से बड़ा है, तो अधिकतम तत्व बाएं आधे में स्थित है
- अन्यथा अधिकतम तत्व दाएं आधे में स्थित है
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int getMaxinSortedAndRorated(int* arr, int low, int high) {
if (high < low) {
return arr[0];
}
if (high == low) {
return arr[high];
}
int mid = low + (high - low) / 2;
if (mid < high && arr[mid + 1] < arr[mid]) {
return arr[mid];
}
if (mid > low && arr[mid] < arr[mid - 1]) {
return arr[mid - 1];
}
if (arr[low] > arr[mid]) {
return getMaxinSortedAndRorated(arr, low, mid - 1);
} else {
return getMaxinSortedAndRorated(arr, mid + 1, high);
}
}
int main() {
int arr[] = {30, 40, 50, 10, 20};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum element = " << getMaxinSortedAndRorated(arr, 0, n - 1) << endl;
return 0;
}
आउटपुट
जब आप उपरोक्त प्रोग्राम को कंपाइल और निष्पादित करते हैं। यह निम्न आउटपुट उत्पन्न करता है -
Maximum element = 50
