ধরুন আমাদের একটি অ্যারে আছে যা সাজানো হয়েছে, এখন সেটি কিছু পিভটে ঘোরানো হয়েছে। পিভট আগে জানা যায়নি। আমাদের সেই অ্যারে থেকে ন্যূনতম উপাদান খুঁজে বের করতে হবে। সুতরাং যদি অ্যারেটি [4,5,5,5,6,8,2,3,4] এর মত হয়, তাহলে সর্বনিম্ন উপাদান হল 2।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
search() নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি arr, low এবং high
লাগে -
যদি low =উচ্চ, তাহলে arr[low]
ফেরত দিন -
মধ্য :=নিম্ন + (উচ্চ - নিম্ন) / 2
-
উত্তর :=inf
-
যদি arr[low]
-
অন্যথায় যখন arr[high]> arr[mid], তারপর ans :=min of arr[mid] এবং search(arr, low, mid)
-
অন্যথায় যখন arr[low] =arr[mid], তারপর ans :=min of arr[low] এবং search(arr, low + 1, high)
-
অন্যথায় যখন arr[high] =arr[mid], তারপর ans :=min of arr[high] এবং search(arr, low, high - 1)
-
উত্তর ফেরত দিন
-
মূল পদ্ধতি থেকে কল সমাধান (সংখ্যা, 0, সংখ্যার আকার – 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 = INT_MAX;
if(arr[low] < arr[mid]){
ans = min(arr[low], search(arr, mid, high));
}
else if (arr[high] > arr[mid]){
ans = min(arr[mid], search(arr, low, mid));
}
else if(arr[low] == arr[mid]){
ans = min(arr[low], search(arr, low + 1, high));
}
else if(arr[high] == arr[mid]){
ans = min(arr[high], search(arr, low, high - 1));
}
return ans;
}
int findMin(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.findMin(v));
} ইনপুট
[4,5,5,5,6,8,2,3,4]
আউটপুট
2
