मान लें हमारे पास एक सरणी A है, जो क्रमबद्ध है। इसमें सभी तत्व दो बार आते हैं, लेकिन एक तत्व केवल एक बार मौजूद है। हमें उस तत्व को ज्ञात करना है। यदि सरणी [1, 1, 3, 3, 4, 4, 5, 6, 6, 7, 7, 9, 9] है, तो एकल तत्व 5 है।
हम इस समस्या को हल करने के लिए बाइनरी सर्च दृष्टिकोण का उपयोग करेंगे। एकल तत्व से पहले सभी तत्वों का पहला घटना सूचकांक 0, 2, 4, ... पर होता है और पहला घटना सूचकांक 1, 3, 5, ... पर होता है लेकिन एकल तत्व के बाद, पहली संख्या की सभी घटनाएं विषम सूचकांक पर होंगी, और दूसरा तत्व सम सूचकांक स्थानों पर होगा।
इसलिए पहले मध्य सूचकांक mid ज्ञात करें, यदि mid सम है, तो A[mid] और A[mid + 1] की तुलना करें, यदि दोनों समान हैं, तो आवश्यकतानुसार बाएं या दाएं जाएं। अन्यथा जब mid विषम है, तो A[mid] और A[mid - 1] की तुलना करें, यदि वे समान हैं, तो आवश्यकतानुसार बाएं या दाएं जाएं।
उदाहरण
#include <iostream>
using namespace std;
void findSingleElement(int *arr, int left, int right) {
if (left > right)
return;
if (left == right) {
cout << "The required element is: " << arr[left];
return;
}
int mid = (left + right) / 2;
if (mid % 2 == 0) {
if (arr[mid] == arr[mid + 1])
findSingleElement(arr, mid + 2, right);
else
findSingleElement(arr, left, mid);
} else {
if (arr[mid] == arr[mid - 1])
findSingleElement(arr, mid + 1, right);
else
findSingleElement(arr, left, mid - 1);
}
}
int main() {
int arr[] = {1, 1, 3, 3, 4, 4, 5, 6, 6, 7, 7, 9, 9};
int len = sizeof(arr) / sizeof(arr[0]);
findSingleElement(arr, 0, len - 1);
}
आउटपुट
The required element is: 5
