एक सॉर्टेड सरणी को किसी अज्ञात पिवट पर रोटेट किया गया है। हमें उस रोटेटेड सरणी में अधिकतम तत्व ढूंढना है।
उदाहरण: [3,4,5,1,2] → अधिकतम 5 है।
समाधान दृष्टिकोण (बाइनरी सर्च)
हम एक संशोधित बाइनरी सर्च का उपयोग करते हैं:
low = 0,high = n-1।- जब
low <= high:mid = low + (high - low)/2।- यदि
arr[low] < arr[mid]: बायां भाग सॉर्टेड है, अधिकतम दाएं में हो सकता है।ans = max(ans, arr[low]),low = mid + 1। - अन्यथा यदि
arr[high] > arr[mid]: दायां भाग सॉर्टेड है, अधिकतम बाएं में हो सकता है।ans = max(ans, arr[mid]),high = mid - 1। - एज केस:
low == midयाhigh == midको संभालें।
ansवापस करें।
C++ कार्यान्वयन (रिकर्सिव)
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int search(vector& arr, int low, int high) {
if (low == high) return arr[low];
int mid = low + (high - low) / 2;
int ans = 0;
if (arr[low] < arr[mid]) {
ans = max(arr[low], search(arr, mid, high));
} else if (arr[high] > arr[mid]) {
ans = max(arr[mid], search(arr, low, mid));
} else if (arr[low] == arr[mid]) {
ans = max(arr[low], search(arr, low + 1, high));
} else if (arr[high] == arr[mid]) {
ans = max(arr[high], search(arr, low, high - 1));
}
return ans;
}
int findMax(vector& nums) {
return search(nums, 0, nums.size() - 1);
}
};
int main() {
Solution ob;
vector v = {4,5,5,5,6,8,2,3,4};
cout << ob.findMax(v);
return 0;
}
इनपुट
[4,5,5,5,6,8,2,3,4]
आउटपुट
8
