বিবেচনা করুন আমরা একটি অ্যারে আছে, যা সাজানো হয়. এটিতে সমস্ত উপাদান রয়েছে দুবার উপস্থিত হয়, তবে একটি উপাদান কেবল একবারের জন্য উপস্থিত থাকে। আমাদের সেই উপাদানটি খুঁজে বের করতে হবে। যদি অ্যারে হয় [1, 1, 3, 3, 4, 4, 5, 6, 6, 7, 7, 9, 9], তাহলে একক উপাদান হল 5৷
আমরা এটি সমাধান করতে বাইনারি অনুসন্ধান পদ্ধতি ব্যবহার করব। একক উপাদানের আগে সমস্ত উপাদানের প্রথম সংঘটন সূচক 0, 2, 4, … এবং প্রথম সংঘটন সূচক 1, 3, 5, … তবে একক উপাদানের পরে, প্রথম সংখ্যার সমস্ত ঘটনা বিজোড় সূচকে হবে, এবং দ্বিতীয় উপাদান সমান সূচক অবস্থানে থাকবে।
তাই প্রথমে মধ্যম সূচক মিড খুঁজুন, যদি মাঝারি জোড় হয়, তাহলে A[মিড] এবং A[মিড + 1] তুলনা করুন, যদি উভয়ই একই হয়, তাহলে প্রয়োজন অনুযায়ী বাম বা ডানে যান। অন্যথায় যখন মধ্য বিজোড় হয়, তখন A[মিড] এবং A[মধ্য – 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
