একটি অ্যারে দেওয়া আছে যা প্রথমে বর্ধমান (increasing) তারপর হ্রাসমান (decreasing)। আমাদের অ্যারেতে সর্বোচ্চ মান খুঁজে বের করতে হবে। উদাহরণস্বরূপ, অ্যারে A = [8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1] হলে আউটপুট হবে ৪৫০।
এটি সমাধানের জন্য বাইনারি সার্চ (binary search) ব্যবহার করা যায়। তিনটি কন্ডিশন (condition) আছে:
- যদি মিড (mid) এলিমেন্ট তার দুটি পাড়ের উপাদান থেকে বড় হয়, তবে মিডই সর্বোচ্চ
- যদি মিড পরবর্তী এলিমেন্ট থেকে বড় হয় কিন্তু পূর্ববর্তী এলিমেন্ট থেকে ছোট হয়, তবে সর্বোচ্চ মিডের বামপাশে আছে
- যদি মিড এলিমেন্ট পরবর্তী এলিমেন্ট থেকে ছোট হয় কিন্তু পূর্ববর্তী এলিমেন্ট থেকে বড় হয়, তবে সর্বোচ্চ মিডের ডানপাশে আছে
উদাহরণ
#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
