C++ का उपयोग करके क्रमबद्ध सरणी में K से बड़े तत्वों की संख्या ज्ञात करना

समस्या विवरण

इस समस्या में, हमें N क्रमबद्ध पूर्णांक मानों वाली एक सरणी arr[] और एक पूर्णांक k दिया गया है। हमारा कार्य क्रमबद्ध सरणी में K से बड़े तत्वों की संख्या ज्ञात करना है।

उदाहरण

इनपुट

arr[] = {1, 2, 5, 7, 8, 9}
k = 4

आउटपुट

4

व्याख्या

K = 4 से बड़े तत्व हैं: 5, 7, 8, 9

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

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

सरणी पर 0 से N तक लूप का उपयोग करके एक सरल समाधान। और फिर पहले तत्व पर रुकें जो k से बड़ा है। फिर शेष मानों की संख्या गिनें।

#include <iostream> 
using namespace std; 

int findGreaterCount(int arr[], int n, int k) {
    for(int i = 0; i < n; i++) {
        if(arr[i] > k)
            return (n - i);
    }
    return 0; // कोई तत्व बड़ा नहीं मिला
}

int main() {
    int arr[] = {1, 3, 5, 7, 7, 8, 12, 21};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    cout << "K से बड़े तत्वों की संख्या है " << findGreaterCount(arr, n, k);
    return 0;
}

विधि 2: बाइनरी खोज (O(log N)) - अधिक कुशल

K से बड़े तत्वों को खोजने के लिए बाइनरी खोज का उपयोग करना। और फिर बड़े तत्वों की संख्या वापस करना।

#include <iostream> 
using namespace std; 

int findGreaterCount(int arr[], int n, int k) {
    int start = 0;
    int end = n - 1;
    int firstGreaterIdx = n; // डिफ़ॉल्ट: कोई तत्व बड़ा नहीं
    
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] > k) {
            firstGreaterIdx = mid;
            end = mid - 1; // बाईं ओर खोजें
        } else {
            start = mid + 1; // दाईं ओर खोजें
        }
    }
    
    return (n - firstGreaterIdx);
}

int main() {
    int arr[] = {1, 3, 5, 7, 7, 8, 12, 21};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    cout << "K से बड़े तत्वों की संख्या है " << findGreaterCount(arr, n, k);
    return 0;
}

आउटपुट

K से बड़े तत्वों की संख्या है 5

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

मुख्य बिंदु

• सरणी क्रमबद्ध होनी चाहिए बाइनरी खोज के लिए
• बाइनरी खोज पहले तत्व का इंडेक्स खोजती है जो k से बड़ा है
• उत्तर = न - firstGreaterIndex
• यदि सभी तत्व ≤ k हैं, तो उत्तर 0 है