พิจารณาว่าเรามีอาร์เรย์ A ซึ่งเรียงลำดับแล้ว มีสมาชิกทุกตัวปรากฏ 2 ครั้ง แต่มีตัวเดียวปรากฏแค่ครั้งเดียว เราต้องหาตัวเลขนั้น ถ้าอาร์เรย์เป็น [1, 1, 3, 3, 4, 4, 5, 6, 6, 7, 7, 9, 9] ตัวเลขที่เดี่ยวคือ 5
เราจะใช้วิธี Binary Search เพื่อแก้ปัญหานี้ สมาชิกทั้งหมดก่อนตัวเดี่ยว มีการเกิดครั้งแรกที่ดัชนี 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
