বিবরণ
বিভিন্ন উপাদান সম্বলিত একটি সোর্ট করা অ্যারে কোনো অজানা পয়েন্টে রোটেট করা আছে, কাজ হলো সেখানে সর্বোচ্চ উপাদান বের করা।
উদাহরণ
ইনপুট অ্যারে যদি {30, 40, 50, 10, 20} হয়, তবে সর্বোচ্চ উপাদান হলো 50।
অ্যালগরিদম
- সর্বোচ্চ উপাদান হলো একমাত্র সেই উপাদান যার পরবর্তী উপাদান তা থেকে ছোট। যদি কোনো পরবর্তী ছোট উপাদান না থাকে, তবে রোটেশন নেই অর্থাৎ শেষ উপাদানই সর্বোচ্চ
- মিডেল এলিমেন্টের জন্য এই শর্তটি যাচাই করি mid – 1 এবং mid + 1 ইনডেক্সের উপাদানদের সাথে তুলনা করে। যদি সর্বোচ্চ উপাদান মিডেলে না থাকে (ন mid, ন mid + 1), তবে সর্বোচ্চ উপাদান বাম বা ডান পার্শ্বে থাকে −
- যদি মিডেল উপাদান শেষ উপাদানের চেয়ে বড় হয়, তবে সর্বোচ্চ উপাদান বাম পার্শ্বে থাকে
- অন্যথায় সর্বোচ্চ উপাদান ডান পার্শ্বে থাকে
উদাহরণ
#include <bits/stdc++.h> using namespace std; int getMaxinSortedAndRorated(int *arr, int low, int high) { if (high < low) { return arr[0]; } if (high == low) { return arr[high]; } int mid = low + (high - low) / 2; if (mid < high && arr[mid + 1] < arr[mid]) { return arr[mid]; } if (mid > low && arr[mid] < arr[mid - 1]) { return arr[mid - 1]; } if (arr[low] > arr[mid]) { return getMaxinSortedAndRorated(arr, low, mid - 1); } else { return getMaxinSortedAndRorated(arr, mid + 1, high); } } int main() { int arr[] = {30, 40, 50, 10, 20}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Maximum element = " << getMaxinSortedAndRorated(arr, 0, n - 1) << endl; return 0; }আউটপুট
প্রোগ্রামটি কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে −
Maximum element = 50
