মনে করুন একটি অ্যারে সর্টেড আছে, কিন্তু সেটি কোনো অজানা পিভট (pivot) বিন্দুতে রোটেট করা হয়েছে। আমাদের কাজ হলো সেই রোটেটেড অ্যারেতে থেকে ন্যূনতম মান বের করা। যেমন অ্যারে [3,4,5,1,2] হলে আউটপুট হবে ১।
সমাধানের ধাপসমূহ:
- low := 0 এবং high := অ্যারের শেষ ইনডেক্স, n := আকার, ans := ইনফিনিটি
- while low ≤ high
- mid := low + (high - low)/2
- যদি arr[low] < arr[mid], তবে ans := min(ans, arr[low]), low := mid + 1
- অথবা যদি arr[high] > arr[mid], তবে ans := min(ans, arr[mid]), high := mid – 1
- অথবা যদি low = mid, তবে ans := min(ans, arr[low]), low := mid + 1
- অথবা যদি high = mid, তবে ans := min(ans, arr[high]), high := mid - 1
- return ans
উদাহরণ
#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
