এই সমস্যায়, আমাদের একটি সাজানো অ্যারে arr[] এবং একটি পূর্ণসংখ্যা মান x দেওয়া হয়েছে। আমাদের কাজ হল একটি সাজানো অ্যারেতে মেঝে খোঁজার জন্য একটি প্রোগ্রাম তৈরি করা .
সর্টেড অ্যারে অ্যারেতে X-এর তল অ্যারে অ্যারের সবচেয়ে বড় উপাদান যা x এর থেকে ছোট বা সমান।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক
Input: arr[] = {2, 5, 6, 8, 9, 12, 21, 25}, x = 10
Output: 9 ব্যাখ্যা − উপরের অ্যারেতে 9 হল বৃহত্তম সংখ্যা যা 10 এর থেকে ছোট বা সমান৷
সমাধান পদ্ধতি
সমস্যাটির একটি সহজ সমাধান হল সরাসরি অ্যারে ট্র্যাভার্স করা এবং শর্ত পূরণ করে এমন উপাদানগুলি খুঁজে বের করা। অ্যারে অতিক্রম করার সময়,
আমরা প্রতিটি উপাদান পরীক্ষা করব, যদি এটি x-এর চেয়ে বড় হয়, তাহলে পূর্ববর্তী উপাদানটিকে x-এর তল হিসাবে ফিরিয়ে দিন।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
int findFloorSortedArray(int arr[], int n, int x){
if (x >= arr[n - 1])
return (n-1);
if (x < arr[0])
return -1;
for (int i = 1; i < n; i++)
if (arr[i] > x)
return (i - 1);
return -1;
}
int main(){
int arr[] = {2, 5, 6, 8, 9, 12, 21, 25};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int floorIndex = findFloorSortedArray(arr, n - 1, x);
if (floorIndex == -1)
cout<<"The floor of "<<x<<" doesn't exist in the array";
else
cout<<"The floor of "<<x<<" in the array is "<<arr[floorIndex];
return 0;
} আউটপুট
The floor of 10 in the array is 9
বিকল্প পদ্ধতি
সমস্যা সমাধানের একটি বিকল্প পদ্ধতি হল বাইনারী সার্চিং অ্যালগরিদম ব্যবহার করে যেমন অ্যারে সাজানো হয় এবং আমাদের কাজটি মান খোঁজার উপর ভিত্তি করে। এই সমাধানে, আমরা অ্যারের মাঝামাঝি সূচকে উপাদানটি অনুসন্ধান করব। তারপর মধ্যম উপাদান অনুসারে, আমরা অ্যারের প্রথমার্ধে (ছোট অর্ধেক) বা দ্বিতীয় অর্ধে (বৃহত্তর অর্ধেক) সংখ্যাটি আরও অনুসন্ধান করব। এবং এটি চালিয়ে যান যতক্ষণ না পুরো অ্যারেটি অতিক্রম করা হয় বা উপাদানটি একটি সাব-অ্যারের মাঝখানে পাওয়া যায়।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
int findFloorSortedArray(int arr[], int start, int end, int x){
if (start > end)
return -1;
if (x >= arr[end])
return end;
int mid = (start + end) / 2;
if (arr[mid] == x)
return mid;
if (mid > 0 && arr[mid - 1] <= x && x < arr[mid])
return mid - 1;
if (x < arr[mid])
return findFloorSortedArray(arr, start, mid - 1, x);
return findFloorSortedArray(arr, mid + 1, end, x);
}
int main(){
int arr[] = {2, 5, 6, 8, 9, 12, 21, 25};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int floorIndex = findFloorSortedArray(arr, 0, n - 1, x);
if (floorIndex == -1)
cout<<"The floor of "<<x<<" doesn't exist in the array";
else
cout<<"The floor of "<<x<<" in the array is "<<arr[floorIndex];
return 0;
} আউটপুট
The floor of 10 in the array is 9
