केवल 0s और 1s वाली क्रमबद्ध संख्याओं की एक सरणी को देखते हुए, संक्रमण बिंदु खोजें। एक संक्रमण बिंदु सरणी में प्रदर्शित होने वाले पहले '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' की अनुक्रमणिका खोजने के लिए बाइनरी खोज विधि का उपयोग करके इसे हल कर सकते हैं।
-
इनपुट एन बाइनरी नंबरों की एक सरणी लें
-
अब एक फ़ंक्शन ट्रांज़िशनपॉइंट (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' के रूप में मिलता है।