इस लेख में, हमें एक समस्या दी गई है, हमें एक एरे दिया गया है, और दो प्रकार की क्वेरी हैं जिनका हमें उत्तर देना है।
- टाइप 0 - हमें x (दिए गए मान) से अधिक या बराबर तत्वों की संख्या की गणना करनी है।
- टाइप 1 - हमें x (दिए गए मान) से सख्ती से अधिक तत्वों की संख्या की गणना करनी है।
यहाँ एक सरल उदाहरण है:
इनपुट: arr[] = {10, 15, 30, 40, 45} और Q = 3
क्वेरी 1: 0 50
क्वेरी 2: 1 40
क्वेरी 3: 0 30
आउटपुट: 0 1 3
व्याख्या: x = 50, q = 0: 50 से अधिक या बराबर कोई तत्व नहीं।
x = 40, q = 1: 45, 40 से अधिक है।
x = 30, q = 0: तीन तत्व 30, 40, 45, 30 से अधिक या बराबर हैं।
समाधान का दृष्टिकोण
हम समाधान खोजने के लिए दो अलग-अलग विधियों का उपयोग कर सकते हैं। पहले हम ब्रूट फोर्स समाधान का उपयोग करेंगे और फिर जांचेंगे कि क्या यह उच्च प्रतिबंधों के लिए काम कर सकता है या नहीं। यदि नहीं, तो हम अपने समाधान को अनुकूलित करने के लिए आगे बढ़ते हैं।
ब्रूट फोर्स दृष्टिकोण
इस दृष्टिकोण में, हम सभी q क्वेरी के लिए एरे के माध्यम से ट्रैवर्स करेंगे और उन संख्याओं को ढूंढेंगे जो दी गई शर्तों को पूरा करती हैं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void query(int *arr, int n, int type, int val) {
int count = 0; // उत्तर
if(!type) { // जब टाइप 0 क्वेरी पूछी जाती है
for(int i = 0; i < n; i++) {
if(arr[i] >= val)
count++;
}
} else { // जब टाइप 1 क्वेरी पूछी जाती है
for(int i = 0; i < n; i++) {
if(arr[i] > val)
count++;
}
}
cout << count << "\n";
}
int main() {
int ARR[] = {10, 15, 30, 40, 45};
int n = sizeof(ARR)/sizeof(ARR[0]); // हमारे एरे का आकार
query(ARR, n, 0, 50); // क्वेरी 1
query(ARR, n, 1, 40); // क्वेरी 2
query(ARR, n, 0, 30); // क्वेरी 3
return 0;
}
आउटपुट
0 1 3
उपरोक्त दृष्टिकोण में, हम केवल एरे के माध्यम से ट्रैवर्स कर रहे हैं और क्वेरी के लिए उत्तर की गणना कर रहे हैं; यह दृष्टिकोण दिए गए उदाहरणों के लिए काम कर रहा है, लेकिन यदि हम उच्च प्रतिबंधों का सामना करते हैं, तो यह दृष्टिकोण विफल हो जाएगा क्योंकि प्रोग्राम की समग्र समय जटिलता O(N*Q) है जहां N हमारे एरे का आकार है और Q क्वेरी की संख्या है, इसलिए अब हम इस दृष्टिकोण को अनुकूलित करेंगे ताकि यह उच्च प्रतिबंधों के लिए भी काम करे।
कुशल दृष्टिकोण
इस दृष्टिकोण में, हम दिए गए मान के अपर बाउंड और लोअर बाउंड को खोजने के लिए बाइनरी सर्च का उपयोग करेंगे। हम पहले बाइनरी सर्च का उपयोग करके अपने एरे को सॉर्ट करते हैं और फिर अपने लोअर बाउंड और अपर बाउंड फंक्शन को तदनुसार लागू करते हैं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void lowerbound(int *arr, int n, int val) {
int l = -1, r = n;
while(r - l > 1) { // उत्तर को बाइनरी सर्च करना
int mid = (l+r)/2;
if(arr[mid] >= val)
r = mid;
else
l = mid;
}
if(r == n) // यदि r अनमूव्ड है तो इसका मतलब है कि कोई तत्व नहीं है जो शर्त को पूरा करता है
cout << "0\n";
else
cout << n - r << "\n";
}
void upperbound(int *arr, int n, int val) {
int l = -1, r = n;
while(r - l > 1) { // उत्तर को बाइनरी सर्च करना
int mid = (l+r)/2;
if(arr[mid] > val)
r = mid;
else
l = mid;
}
if(r == n)// यदि r अनमूव्ड है तो इसका मतलब है कि कोई तत्व नहीं है जो शर्त को पूरा करता है
cout << "0\n";
else
cout << n - r << "\n";
}
void query(int *arr, int n, int type, int val) {
if(!type) // यदि टाइप == 0 तो हम लोअर बाउंड फंक्शन कॉल करते हैं
lowerbound(arr, n, val);
else // यदि टाइप == 1 तो हम अपरबाउंड फंक्शन कॉल करते हैं
upperbound(arr, n, val);
}
int main() {
int arr[] = {1, 2, 3, 4};
int n = sizeof(arr)/sizeof(arr[0]); // हमारे एरे का आकार
sort(arr, arr+n); // एरे को सॉर्ट करना
query(arr, n, 0, 5); // क्वेरी 1
query(arr, n, 1, 3); // क्वेरी 2
query(arr, n, 0, 3); // क्वेरी 3
return 0;
}
आउटपुट
0 1 2
उपरोक्त कोड बाइनरी सर्च पर काम करता है जो हमारी समय जटिलता को काफी कम कर देता है। इस प्रकार हमारी अंतिम जटिलता O(NlogN) हो जाती है, जहां N हमारे एरे का आकार है।
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम दिए गए मान के अपर बाउंड और लोअर बाउंड को खोजने के लिए बाइनरी सर्च का उपयोग करेंगे। अब बाइनरी सर्च के लिए, हम पहले अपने एरे को सॉर्ट करते हैं क्योंकि यह केवल सॉर्टेड एरे के साथ काम करता है। हम अपना लोअर बाउंड और अपर बाउंड फंक्शन बनाते हैं जो हमें क्रमशः टाइप 0, टाइप 1 शर्तों को पूरा करने वाली पहली संख्या खोजने में मदद करता है। अब चूंकि हमने एरे को सॉर्ट कर दिया है, हमें वह पहली संख्या मिल गई जो शर्त को पूरा करती है, इसलिए इस तत्व के बाद के तत्व भी शर्त का पालन करते हैं, इसलिए हम इस तत्व के इंडेक्स और N (हमारे एरे का आकार) के अंतर को प्रिंट करते हैं।
निष्कर्ष
इस लेख में, हम बाइनरी सर्च का उपयोग करके "ग्रेटर दैन" और "नॉट लेस दैन" के लिए क्वेरी हल करने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और इसे हल करने के पूर्ण दृष्टिकोण (सामान्य और कुशल) को भी सीखा। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह लेख मददगार लगा होगा।
