এই C++ প্রোগ্রামে, আমরা বাইনারি সার্চ পদ্ধতি ব্যবহার করে অ্যারেতে একটি শীর্ষ উপাদান (peak element) খুঁজে বের করব। এই অ্যালগরিদম প্রথমে পাওয়া শীর্ষ উপাদানটি ফেরত দেয় এবং এর সময় জটিলতা O(log n)।
অ্যালগরিদম
শুরু PeakElement() ফাংশনে 'arr' অ্যারে, শুরু এবং শেষ ইনডেক্স আর্গুমেন্ট হিসেবে থাকে। অ্যারের উপ-ভাগের মাঝপথ (mid) বরাদ্দ করুন। যদি mid সীমানার ইনডেক্সে থাকে এবং mid-এর মান এর প্রতিবেশীর চেয়ে বেশি হয়, তবে mid কো শীর্ষ হিসেবে ফেরত দিন। যদি mid-এর মান তার দুটি প্রতিবেশীর চেয়ে বেশি হয়, তবে mid কো শীর্ষ হিসেবে ফেরত দিন। যদি mid-এর ডানের মান mid-এর চেয়ে বেশি হয়, তবে অ্যারের দ্বিতীয় উপ-ভাগকে PeakElement()-এ আর্গুমেন্ট হিসেবে পাঠান। যদি mid-এর বামের মান mid-এর চেয়ে বেশি হয়, তবে অ্যারের প্রথম উপ-ভাগকে PeakElement()-এ আর্গুমেন্ট হিসেবে পাঠান। শেষ
উদাহরণ কোড
#include <iostream>
using namespace std;
int PeakElement(int a[], int start, int end) {
int i, mid;
mid = (end + start + 1) / 2;
if ((a[mid] > a[mid + 1] && mid == start) || (a[mid] > a[mid - 1] && mid == end)) {
return a[mid];
} else if (a[mid] < a[mid - 1] && a[mid] > a[mid + 1]) {
return a[mid];
} else if (a[mid] <= a[mid + 1]) {
return PeakElement(a, mid + 1, end);
} else if (a[mid] <= a[mid - 1]) {
return PeakElement(a, start, mid - 1);
}
}
int main() {
int n, i, p;
cout << "\nডাটা উপাদানের সংখ্যা লিখুন: ";
cin >> n;
int arr[n];
for (i = 0; i < n; i++) {
cout << "এলিমেন্ট " << i + 1 << ": ";
cin >> arr[i];
}
p = PeakElement(arr, 0, n - 1);
cout << "\nদেওয়া অ্যারের শীর্ষ উপাদানটি হল: " << p;
return 0;
}
আউটপুট
ডাটা উপাদানের সংখ্যা লিখুন: 5 এলিমেন্ট 1: 45 এলিমেন্ট 2: 26 এলিমেন্ট 3: 70 এলিমেন্ট 4: 60 এলিমেন্ট 5: 15 দেওয়া অ্যারের শীর্ষ উপাদানটি হল: 70
