ধরুন আমাদের একটি অ্যারে আছে, যেটি প্রথমে বাড়ছে তারপর কমছে। আমাদের অ্যারেতে সর্বোচ্চ মান খুঁজে বের করতে হবে। সুতরাং যদি অ্যারের উপাদানগুলি A =[8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1] এর মতো হয়, তাহলে আউটপুট হবে 500৷
আমরা এটি সমাধান করতে বাইনারি অনুসন্ধান ব্যবহার করতে পারি। তিনটি শর্ত আছে -
- যখন মাঝামাঝি তার সংলগ্ন উপাদানগুলির উভয়ের চেয়ে বড় হয়, তখন মাঝারিটি সর্বাধিক হয়
- যদি মাঝামাঝি পরবর্তী উপাদানের থেকে বড় হয়, কিন্তু পূর্ববর্তী উপাদানের থেকে ছোট হয়, তাহলে সর্বোচ্চটি মধ্যভাগের বাম দিকে থাকে৷
- যদি মধ্য মৌলটি পরবর্তী উপাদানের চেয়ে ছোট হয়, কিন্তু পূর্ববর্তী উপাদানের চেয়ে বড় হয়, তাহলে সর্বোচ্চটি মধ্যভাগের ডানদিকে থাকে৷
উদাহরণ
#include<iostream>
using namespace std;
int getMaxElement(int array[], int left, int right) {
if (left == right)
return array[left];
if ((right == left + 1) && array[left] >= array[right])
return array[left];
if ((right == left + 1) && array[left] < array[right])
return array[right];
int mid = (left + right)/2;
if ( array[mid] > array[mid + 1] && array[mid] > array[mid - 1])
return array[mid];
if (array[mid] > array[mid + 1] && array[mid] < array[mid - 1])
return getMaxElement(array, left, mid-1);
else
return getMaxElement(array, mid + 1, right);
}
int main() {
int array[] = {8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1};
int n = sizeof(array)/sizeof(array[0]);
cout << "The maximum element is: " << getMaxElement(array, 0, n-1);
} আউটপুট
The maximum element is: 450
