ধরুন একটি অ্যারে আছে, এবং এটি সাজানো হয়েছে, বিবেচনা করুন যে অ্যারেটি কিছু পিভটে ঘোরানো হয়েছে, যা আমাদের অজানা। তাই আমাদের সেই ঘোরানো অ্যারে থেকে সর্বনিম্ন খুঁজে বের করতে হবে। সুতরাং অ্যারে যদি [3,4,5,1,2] এর মত হয়, তাহলে আউটপুট হবে 1।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- নিম্ন :=0 এবং উচ্চ :=অ্যারের শেষ সূচক, n :=অ্যারের আকার, উত্তর :=অসীম
- যখন কম <=উচ্চ
- মধ্য :=নিম্ন + (উচ্চ - নিম্ন)/2
- যদি arr[low]
- অন্যথায় যদি arr[high]> arr[mid] হয়, তাহলে ans :=ans এবং arr[mid], high :=mid – 1
- অন্যথায় নিম্ন =মধ্য, তাহলে 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 findMin(vector<int>& arr) {
int low = 0;
int high = arr.size() - 1;
int n = arr.size();
int ans = INT_MAX;
while(low <= high){
int mid = low + (high - low) / 2;
if(arr[low] < arr[mid]){
ans = min(ans, arr[low]);
low = mid + 1;
} else if(arr[high] > arr[mid]) {
ans = min(ans, arr[mid]);
high = mid - 1;
} else if(low == mid) {
ans = min(ans, arr[low]);
low = mid + 1;
} else if(high == mid) {
ans = min(ans, arr[high]);
high = mid - 1;
}
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {15,35,85,96,5,6,8,12};
cout << ob.findMin(v);
} ইনপুট
[15,35,85,96,5,6,8,12]
আউটপুট
5
