Cho mảng A đã sắp xếp. Tất cả phần tử xuất hiện 2 lần, chỉ có 1 phần tử xuất hiện 1 lần. Tìm phần tử đó. Ví dụ [1,1,3,3,4,4,5,6,6,7,7,9,9] thì phần tử đơn lẻ là 5.
Dùng tìm kiếm nhị phân. Phần tử trước phần tử đơn lẻ có lần xuất hiện đầu ở chỉ số chẵn (0,2,4...), sau phần tử đơn lẻ thì ngược lại.
Ví dụ mã nguồn
#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);
}
Kết quả đầu ra
The required element is: 5