Hãy xem xét chúng ta có một mảng A, được sắp xếp. Nó có tất cả các phần tử xuất hiện hai lần, nhưng một phần tử chỉ xuất hiện một lần. Chúng ta phải tìm ra yếu tố đó. Nếu mảng là [1, 1, 3, 3, 4, 4, 5, 6, 6, 7, 7, 9, 9], thì phần tử đơn là 5.
Chúng tôi sẽ sử dụng phương pháp tìm kiếm nhị phân để giải quyết vấn đề này. Tất cả các phần tử trước phần tử đơn lẻ có lần xuất hiện đầu tiên ở chỉ số 0, 2, 4,… và lần xuất hiện đầu tiên ở chỉ số 1, 3, 5,… nhưng sau phần tử đơn lẻ, tất cả các lần xuất hiện của số đầu tiên sẽ ở chỉ số lẻ, và phần tử thứ hai sẽ ở các vị trí chỉ mục chẵn.
Vì vậy, đầu tiên bạn hãy tìm chỉ số giữa mid, nếu mid chẵn thì so sánh A [mid] và A [mid + 1], nếu cả hai đều giống nhau thì chuyển sang trái hoặc phải tùy theo yêu cầu. Ngược lại, khi giá trị giữa là số lẻ, hãy so sánh A [giữa] và A [giữa - 1], nếu chúng giống nhau thì chuyển sang trái hoặc phải theo yêu cầu.
Ví dụ
#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);
} Đầu ra
The required element is: 5