अवधारणा
दिए गए सरणी array[] के संबंध में जिसमें n विशिष्ट पूर्णांक हैं, तत्व आरोही क्रम में एक लापता तत्व के साथ क्रमिक रूप से रखे गए हैं। हमारा कार्य लापता तत्व निर्धारित करना है।
इनपुट
array[] = {1, 2, 3, 4, 5, 6, 7, 9}
आउटपुट
8
इनपुट
array[] = {-4, -2, -1, 0, 1, 2}
आउटपुट
-3
इनपुट
array[] = {1, 2, 3, 4}
आउटपुट
-1
कोई तत्व लापता नहीं है।
विधि
सिद्धांत
असंगति देखें: इस सिद्धांत के अनुसार, किसी भी तत्व और उसके सूचकांक के बीच का अंतर हर तत्व के लिए array[0] होना चाहिए।
उदाहरण,
A[] = {1, 2, 3, 4, 5} -> सुसंगत
B[] = {201, 202, 203, 204} -> सुसंगत
C[] = {1, 2, 3, 5, 6} -> असंगत क्योंकि C[3] - 3 != C[0] यानी 5 - 3 != 1
असंगति निर्धारित करने से प्रत्येक बार सरणी के केवल आधे हिस्से को O(logN) में स्कैन करने में मदद मिलती है।
एल्गोरिदम
मध्य तत्व ढूंढें और जांचें कि क्या यह सुसंगत है।
यदि मध्य तत्व सुसंगत है, तो जांचें कि मध्य तत्व और उसके अगले तत्व के बीच का अंतर 1 से अधिक है यानी जांचें कि array[mid + 1] - array[mid] > 1
यदि हां, तो array[mid] + 1 लापता तत्व है।
अन्यथा, हमें मध्य तत्व से सरणी के दाएं आधे हिस्से को स्कैन करना होगा और चरण-1 पर जाना होगा।
यदि मध्य तत्व असंगत है, तो जांचें कि मध्य तत्व और उसके पिछले तत्व के बीच का अंतर 1 से अधिक है यानी जांचें कि array[mid] - array[mid - 1] > 1
यदि हां, तो array[mid] - 1 लापता तत्व है।
अन्यथा, हमें मध्य तत्व से सरणी के बाएं आधे हिस्से को स्कैन करना होगा और चरण-1 पर जाना होगा।
उदाहरण
// दृष्टिकोण का CPP कार्यान्वयन #include<bits/stdc++.h> using namespace std; // लापता तत्व लौटाने के लिए फ़ंक्शन दिखाता है int findMissing(int array[], int n1){ int low = 0, high = n1 - 1; int mid1; while (high > low){ mid1 = low + (high - low) / 2; // जांचें कि क्या मध्य तत्व सुसंगत है if (array[mid1] - mid1 == array[0]){ // मध्य तत्वों तक कोई असंगति नहीं // जब लापता तत्व ठीक मध्य तत्व के बाद है if (array[mid1 + 1] - array[mid1] > 1) return array[mid1] + 1; else{ // दाएं जाएं low = mid1 + 1; } } else{ // यहां असंगति मिली // जब लापता तत्व ठीक मध्य तत्व के पहले है if (array[mid1] - array[mid1 - 1] > 1) return array[mid1] - 1; else{ // बाएं जाएं high = mid1 - 1; } } } // यहां, कोई लापता तत्व नहीं मिला return -1; } // ड्राइवर कोड int main(){ int array[] = { -9, -8, -6, -5, -4, -3, -2, -1, 0 }; int n1 = sizeof(array)/sizeof(array[0]); cout <<"लापता तत्व:" <<(findMissing(array, n1)); }
आउटपुट
लापता तत्व:-7