केवल 0 और 1 वाली सॉर्टेड संख्याओं की एक सरणी दी गई है, ट्रांजिशन पॉइंट खोजें। एक ट्रांजिशन पॉइंट सरणी में पहली बार आने वाले '1' का इंडेक्स है। उदाहरण के लिए,
इनपुट-1 -
N = 6 arr[] = {0, 0, 0, 0, 1, 1}
आउटपुट -
4
व्याख्या - चूंकि दी गई सरणी में 0 और 1 हैं, हम देख सकते हैं कि इंडेक्स '4' पर तत्व संख्या '1' रखता है।
इनपुट-2 -
N = 5 arr[] = {0, 0, 1, 1, 1}
आउटपुट -
2
व्याख्या - दी गई सरणी में 0 और 1 हैं, हम देख सकते हैं कि इंडेक्स '2' पर तत्व संख्या '1' रखता है। इस प्रकार, हम 2 लौटाएंगे।
इस प्रॉब्लम को हल करने का दृष्टिकोण
दिए गए पूर्णांकों की सरणी में, हमें पहले 1 का इंडेक्स ढूंढना है। इस विशेष प्रॉब्लम को हल करने के लिए, हम बाइनरी सर्च मेथड का उपयोग करके पहले '1' का इंडेक्स ढूंढ सकते हैं।
N बाइनरी नंबर्स की एक सरणी का इनपुट लें
अब एक फंक्शन transitionPoint(int *arr, int n) एक सरणी को इनपुट के रूप में लेता है और उसका आकार और सरणी में पहली बार आने वाले '1' का इंडेक्स लौटाता है।
दो पॉइंटर्स लो, हाई लें जो '0' और '1' के रूप में इनिशियलाइज़ हों।
अब हम सरणी का मध्य बिंदु ढूंढेंगे और जांचेंगे कि क्या यह '1' है या नहीं।
यदि सरणी का मध्य '1' है तो हम उसका इंडेक्स लौटाएंगे अन्यथा हम आगे बढ़कर जांच करेंगे।
लो पॉइंटर को बढ़ाएं और फिर '1' के लिए जांच करें।
चरणों को तब तक दोहराएं जब तक हमें '1' न मिल जाए।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int transitionPoint(int *arr, int n) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == 0)
low = mid + 1;
else if (arr[mid] == 1) {
if (mid == 0 || (mid > 0 && arr[mid - 1] == 0))
return mid;
high = mid - 1;
}
}
return -1;
}
int main() {
int n = 6;
int arr[n] = {0, 0, 0, 1, 1, 1};
int ans = transitionPoint(arr, n);
if (ans >= 0) {
cout << "Transition Point is: " << ans << endl;
} else {
cout << "Not Found" << endl;
}
return 0;
}
आउटपुट
उपरोक्त कोड चलाने पर निम्न आउटपुट उत्पन्न होगा,
Transition Point is: 3
दी गई सरणी {0, 0, 0, 1, 1, 1} में तत्व '1' इंडेक्स '3' पर मौजूद है, इस प्रकार हमें आउटपुट के रूप में '3' मिलता है।
