C++-এ রোটেটেড সর্টেড অ্যারেতে সর্বোচ্চ মান বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি সর্টেড অ্যারে কতটুকু রোটেট করা আছে (pivot অজানা), সেটি দেওয়া থাকলে সেটি থেকে সর্বোচ্চ মান বের করতে হবে।

উদাহরণ: [3,4,5,1,2] → সর্বোচ্চ 5।

সমাধানের পদ্ধতি (বাইনারি সার্চ ভিত্তিক)

রিকার্সিভ বাইনারি সার্চ ব্যবহার করে:

1. low=0, high=n-1।
2. যদি low == high, তবে arr[low] রিটার্ন।
3. mid = low + (high-low)/2।
4. যদি arr[low] < arr[mid]: বাম পার্ট সর্টেড, সর্বোচ্চ ডানপাশে বা arr[low]-এ। রিকার্সিভ কল: search(arr, mid, high)।
5. যদি arr[high] > arr[mid]: ডানপাশ সর্টেড, সর্বোচ্চ বামপাশে বা arr[mid]-এ। রিকার্সিভ কল: search(arr, low, mid)।
6. যদি arr[low] == arr[mid]: ডুপ্লিকেট হ্যান্ডলিং, search(arr, low+1, high)।
7. যদি arr[high] == arr[mid]: search(arr, low, high-1)।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int search(vector& arr, int low, int high) {
        if (low == high) return arr[low];
        int mid = low + (high - low) / 2;
        int ans = 0;
        if (arr[low] < arr[mid]) {
            ans = max(arr[low], search(arr, mid, high));
        } else if (arr[high] > arr[mid]) {
            ans = max(arr[mid], search(arr, low, mid));
        } else if (arr[low] == arr[mid]) {
            ans = max(arr[low], search(arr, low + 1, high));
        } else if (arr[high] == arr[mid]) {
            ans = max(arr[high], search(arr, low, high - 1));
        }
        return ans;
    }
    int findMax(vector& nums) {
        return search(nums, 0, nums.size() - 1);
    }
};

int main() {
    Solution ob;
    vector v = {4,5,5,5,6,8,2,3,4};
    cout << ob.findMax(v);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: [4,5,5,5,6,8,2,3,4]

আউটপুট: 8

জটিলতা

• গড় সময়: O(log n)
• সর্বোচ্চ সময়: O(n) — সব মান একই হলে (ডুপ্লিকেট হ্যান্ডলিং)
• স্থান: O(log n) — রিকার্সন স্ট্যাক