ধরুন আমাদের n উপাদান সহ একটি অ্যারে 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
