इस समस्या में, हमें क्रमबद्ध क्रम में बूलियन मानों (केवल 0 और 1 के) से युक्त एक सरणी बिन [] दिया जाता है। हमारा काम है 0 और 1 के क्रमबद्ध सरणी में पहले 1 की अनुक्रमणिका ढूंढना ।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
Input : bin[] = {0, 0, 0, 1, 1}
Output : 3 स्पष्टीकरण -
First 1 of the binary array is encountered at index 3.
समाधान दृष्टिकोण
समस्या को हल करने के लिए, हमें मूल रूप से सरणी में पहली 1 की अनुक्रमणिका खोजने की आवश्यकता है। उसके लिए हम एक खोज तकनीक का उपयोग कर सकते हैं।
एक दृष्टिकोण रैखिक खोज का उपयोग किया जा सकता है, हम सरणी को अनुक्रमणिका 0 से सरणी के अंत तक पार करेंगे। और सरणी में पहले 1 की अनुक्रमणिका लौटाएं, अन्यथा -1 प्रिंट करें।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <iostream>
using namespace std;
double find1stOneInArray(int bin[], int n) {
for (int i = 0; i < n; i++)
if (bin[i] == 1)
return i;
return -1;
}
int main() {
int bin[] = { 0, 0, 0, 1, 1, 1 };
int n = sizeof(bin) / sizeof(bin[0]);
cout<<"The index of 1st occurrence of 1 in array is "<<find1stOneInArray(bin,n);
return 0;
} आउटपुट
The index of 1st occurrence of 1 in array is 3
एक और खोज तकनीक इसका उपयोग बाइनरी सर्च के रूप में किया जा सकता है क्योंकि सरणी को सॉर्ट किया जाता है।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <iostream>
using namespace std;
double find1stOneInArray(int bin[], int n) {
int low = 0;
int high = (n - 1);
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 n = sizeof(bin) / sizeof(bin[0]);
cout<<"The index of 1st occurrence of 1 in array is "<<find1stOneInArray(bin,n);
return 0;
} आउटपुट
The index of 1st occurrence of 1 in array is 3