C++ में क्रमबद्ध सरणी में फ्लोर खोजना

समस्या विवरण

इस समस्या में, हमें एक क्रमबद्ध सरणी arr[] और एक पूर्णांक मान x दिया गया है। हमारा कार्य क्रमबद्ध सरणी में फ्लोर खोजने के लिए एक प्रोग्राम बनाना है।

क्रमबद्ध सरणी arr में X का फ्लोर सरणी arr[] का सबसे बड़ा तत्व है जो x से छोटा या बराबर है।

उदाहरण

इनपुट: arr[] = {2, 5, 6, 8, 9, 12, 21, 25}, x = 10
आउटपुट: 9

व्याख्या - उपरोक्त सरणी में 9 सबसे बड़ी संख्या है जो 10 से छोटी या बराबर है।

हल का दृष्टिकोण

विधि 1: रैखिक खोज (O(N))

समस्या का एक सरल समाधान सीधे सरणी को पार करके और शर्त को संतुष्ट करने वाले तत्वों को खोजना है। सरणी को पार करते समय, हम प्रत्येक तत्व की जांच करेंगे, यदि यह 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, x);
    if (floorIndex == -1)
        cout << "सरणी में " << x << " का फ्लोर मौजूद नहीं है";
    else
        cout << "सरणी में " << x << " का फ्लोर है " << arr[floorIndex];
    return 0;
}

विधि 2: बाइनरी खोज (O(log N)) - इष्टतम

समस्या को हल करने का एक वैकल्पिक तरीका बाइनरी खोज एल्गोरिदम का उपयोग करना है क्योंकि सरणी क्रमबद्ध है और हमारा कार्य मान खोजने पर आधारित है। इस समाधान में, हम सरणी के मध्य इंडेक्स पर तत्व खोजेंगे। फिर मध्य तत्व के अनुसार, हम संख्या को पहले आधे (छोटे आधे) या दूसरे आधे (बड़े आधे) में खोजेंगे। और तब तक जारी रखेंगे जब तक पूरी सरणी पार न हो जाए या तत्व उप-सरणी के मध्य में मिल जाए।

#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 << "सरणी में " << x << " का फ्लोर मौजूद नहीं है";
    else
        cout << "सरणी में " << x << " का फ्लोर है " << arr[floorIndex];
    return 0;
}

आउटपुट

सरणी में 10 का फ्लोर है 9

जटिलता विश्लेषण

विधि	समय जटिलता	स्पेस जटिलता
रैखिक खोज	O(N)	O(1)
बाइनरी खोज	O(log N)	O(log N) पुनरावर्ती / O(1) पुनरावृत्तिमूलक