सी ++ में एक सरणी में स्थानीय मिनीमा खोजें

मान लीजिए कि हमारे पास n तत्वों के साथ एक सरणी A है। हमें सरणी का स्थानीय न्यूनतम ज्ञात करना है। सरणी ए में, तत्व ए [एक्स] को स्थानीय मिनीमा कहा जाता है यदि यह अपने दोनों पड़ोसियों से कम या बराबर है। कोने के तत्वों के लिए केवल एक पड़ोसी पर विचार किया जाएगा। और यदि एक से अधिक स्थानीय मिनीमा उपलब्ध हैं, तो केवल एक ही लौटाएं। उदाहरण के लिए, यदि सरणी [9, 6, 3, 14, 5, 7, 4] जैसी है, तो स्थानीय मिनीमा 3, 5 और 4 हो सकती है, इसलिए यह एल्गोरिथम उनमें से केवल एक को लौटा सकता है।

इस समस्या को हल करने के लिए हम बाइनरी सर्च जैसे लॉजिक को फॉलो करेंगे। यदि मध्य तत्व अपने बाएँ और दाएँ तत्वों से छोटा है, तो मध्य वापस आएँ, अन्यथा, यदि यह बाएँ पड़ोसी से बड़ा है, तो बाईं ओर कुछ स्थानीय मिनीमा हो सकता है, यदि यह दाएँ तत्व से बड़ा है, तो वहाँ दाईं ओर कुछ स्थानीय मिनीमा होंगे, सटीक स्थानीय मिनीमा खोजने के लिए उनके लिए वही कार्य करें।

उदाहरण

#include<iostream>
using namespace std;
int localMinima(int arr[], int left, int right, int n) {
   int mid = left + (right - left)/2;
   if ((mid == 0 || arr[mid-1] > arr[mid]) && (mid == n-1 || arr[mid+1] > arr[mid]))
      return mid;
   else if (mid > 0 && arr[mid-1] < arr[mid])
      return localMinima(arr, left, (mid -1), n);
   return localMinima(arr, (mid + 1), right, n);
}
int findLocalMinima(int arr[], int n) {
   return localMinima(arr, 0, n-1, n);
}
int main() {
   int arr[] = {9, 6, 3, 14, 5, 7, 4};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Local minima is: " << arr[findLocalMinima(arr, n)];
}

आउटपुट

Local minima is: 3