พิจารณาว่าเรามีอาร์เรย์ 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
