इस समस्या में, हमें एक क्रमबद्ध सरणी गिरफ्तारी [] और एक पूर्णांक मान x दिया जाता है। हमारा काम एक प्रोग्राम बनाना है जो एक क्रमबद्ध सरणी में मंजिल को खोजने के लिए . है ।
फ्लोर ऑफ़ X इन सॉर्टेड एरे एरर सरणी arr[] का सबसे बड़ा तत्व है जो 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