मान लीजिए हमारे पास n तत्वों की एक सरणी A है। हमें सरणी का स्थानीय न्यूनतम ढूंढना है। सरणी A में, तत्व A[x] को स्थानीय न्यूनतम कहा जाता है यदि यह अपने दोनों पड़ोसियों से कम या बराबर है। कोने के तत्वों के लिए केवल एक पड़ोसी माना जाएगा। और यदि एक से अधिक स्थानीय न्यूनतम उपलब्ध हैं, तो केवल एक वापस करें। उदाहरण के लिए, यदि सरणी [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
