ধরুন একটি অ্যারে আছে, এবং এটি সাজানো হয়েছে, বিবেচনা করুন যে অ্যারে কিছু পিভটে ঘোরানো হয়েছে, যা আমাদের অজানা। তাই আমাদের সেই ঘূর্ণিত অ্যারে থেকে সর্বাধিক খুঁজে বের করতে হবে। সুতরাং যদি অ্যারে [3,4,5,1,2] এর মত হয়, তাহলে আউটপুট হবে 5।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
নিম্ন :=0 এবং উচ্চ :=অ্যারের শেষ সূচক, n :=অ্যারের আকার, উত্তর :=0
-
যখন কম <=উচ্চ
-
মধ্য :=নিম্ন + (উচ্চ - নিম্ন)/2
-
যদি arr[low]
-
অন্যথায় যদি arr[high]> arr[mid], তাহলে ans :=ans এর সর্বোচ্চ এবং arr[mid], high :=mid – 1
-
অন্যথায় যদি low =mid, তাহলে ans :=ans এর সর্বোচ্চ এবং arr[low], low :=mid + 1
-
অন্যথায় যদি উচ্চ =মধ্য, তাহলে ans :=ans এর সর্বোচ্চ এবং arr[high], high :=mid - 1
-
-
উত্তর ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int search(vector <int>& 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<int>& nums) {
return search(nums, 0, nums.size() - 1);
}
};
main(){
Solution ob;
vector<int> v = {4,5,5,5,6,8,2,3,4};
cout <<(ob.findMax(v));
} ইনপুট
[4,5,5,5,6,8,2,3,4]
আউটপুট
8
