इस समस्या में, हमें एक अनंत सरणी बिन [] दिया जाता है जिसमें क्रमबद्ध क्रम में बूलियन मान (केवल 0 और 1) होते हैं। हमारा काम है 0 और 1 के अनंत क्रमबद्ध सरणी में पहले 1 की अनुक्रमणिका ढूंढना ।
यहां, हमारे पास एक अनंत सरणी है जो गारंटी देता है कि सरणी में 1 मौजूद है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
Input : bin[] = {0, 0, 0, 1, 1, ....}
Output : 3 स्पष्टीकरण -
First 1 of the binary array is encountered at index 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<<"The index of 1st occurrence of 1 in infinite array is "<<find1stOneInfiniteArray(bin);
return 0;
} आउटपुट
The index of 1st occurrence of 1 in infinite array is 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<<"The index of 1st occurrence of 1 in infinite array is " <<find1stOneInfiniteArray(bin,low, high);
return 0;
} आउटपुट
The index of 1st occurrence of 1 in infinite array is 3