এই সমস্যাতে, আমাদের একটি সর্টেড অ্যারে arr[] এবং একটি ইন্টিজার মান x দেওয়া আছে। আমাদের কাজ হল সর্টেড অ্যারেতে ফ্লোর (Floor) বের করার প্রোগ্রাম তৈরি করা।
সর্টেড অ্যারে arr-এ X-এর ফ্লোর হল অ্যারে arr[]-এর সবচেয়ে বড় এলিমেন্ট যা x-র চেয়ে ছোট বা সমান।
উদাহরণ দেখি:
ইনপুট: arr[] = {2, 5, 6, 8, 9, 12, 21, 25}, x = 10 আউটপুট: 9
ব্যাখ্যা - উপরের অ্যারেতে ৯ হল সবচেয়ে বড় সংখ্যা যা ১০-র চেয়ে ছোট বা সমান।
সমাধানের পদ্ধতি
একটি সহজ পদ্ধতি হল সরাসরি অ্যারে ট্রাভার্স করে কন্ডিশন সন্তুষ্টকারী এলিমেন্ট বের করা। অ্যারে ট্রাভার্স করার সময়,
প্রতিটি এলিমেন্ট চেক করব, যদি সেটি 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
