इस समस्या में, हमें एक अनंत सरणी bin[] दी गई है जिसमें बूलियन मान (केवल 0 और 1) सॉर्टेड क्रम में हैं। हमारा कार्य 0 और 1 की अनंत सॉर्टेड सरणी में पहले 1 का इंडेक्स ज्ञात करना है।
यहां, हमारे पास एक अनंत सरणी है जो गारंटी देती है कि सरणी में 1 मौजूद है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट : bin[] = {0, 0, 0, 1, 1, ....} आउटपुट : 3 व्याख्या −
बाइनरी सरणी में पहले 1 का सामना इंडेक्स 3 पर होता है।
समाधान दृष्टिकोण
समस्या को हल करने के लिए, हमें मूल रूप से सरणी में पहले 1 का इंडेक्स ढूंढना होगा। उसके लिए हम एक खोज तकनीक का उपयोग कर सकते हैं।
एक दृष्टिकोण रैखिक खोज का उपयोग करना हो सकता है, हम एक अनंत लूप का उपयोग करके सरणी को पार करेंगे। और सरणी में पहले 1 का इंडेक्स लौटाएंगे, अन्यथा -1 प्रिंट करें।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include <iostream> using namespace std; double find1stOneInfiniteArray(int bin[]) { int i = 0; while(1){ if (bin[i] == 1) return i; i++; } return -1; } int main() { int bin[] = { 0, 0, 0, 1, 1, 1 }; cout<<"अनंत सरणी में 1 की पहली घटना का इंडेक्स है "<<find1stOneInfiniteArray(bin); return 0; } आउटपुट
अनंत सरणी में 1 की पहली घटना का इंडेक्स है 3
एक अन्य खोज तकनीक जिसका उपयोग किया जा सकता है वह है बाइनरी सर्च क्योंकि सरणी सॉर्टेड है।
बस हमें एल्गोरिदम को अपडेट करने की आवश्यकता है क्योंकि कोई ऊपरी सीमा नहीं है, हम इंडेक्स मान 1 से शुरू करके पहले 1 की घटना के इंडेक्स तक उच्च के मान को दोगुना करके इसे ढूंढेंगे।
इन सीमाओं का उपयोग करके, हम बाइनरी सर्च का उपयोग करके इंडेक्स ढूंढ सकते हैं।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include <iostream> using namespace std; double find1stOneInfiniteArray(int bin[], int low, int high) { int mid; while (low <= high) { mid = (low + high) / 2; if (bin[mid] == 1 && (mid == 0 || bin[mid - 1] == 0)) return mid; else if (bin[mid] == 1) high = mid - 1; else low = mid + 1; } return -1; } int main() { int bin[] = { 0, 0, 0, 1, 1, 1, 1 }; int low = 0; int high = 1; while(bin[high] != 1){ low = high; high *= 2; } cout<<"अनंत सरणी में 1 की पहली घटना का इंडेक्स है " <<find1stOneInfiniteArray(bin,low, high); return 0; } आउटपुट
अनंत सरणी में 1 की पहली घटना का इंडेक्स है 3
