Hãy xem xét chúng ta có một mảng A với vài phần tử. Ta có hai giá trị khác X và k. Nhiệm vụ của chúng ta là tìm k số phần tử gần nhất của X từ mảng A. Nếu phần tử X có trong mảng thì nó sẽ không được hiển thị trong đầu ra. Nếu A =[12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56] và X =35, k =4. Kết quả sẽ là 30, 39, 42, 45 .
Để giải quyết vấn đề này, chúng tôi sẽ sử dụng phương pháp tìm kiếm nhị phân. Sử dụng điều này, chúng tôi sẽ nhận được điểm giao nhau. Nếu chỉ số của điểm giao nhau được tìm thấy, chúng ta có thể in k phần tử gần nhất trong thời gian O (k).
Ví dụ
#include<iostream>
using namespace std;
int getCrossoverPoint(int arr[], int left, int right, int x) {
if (arr[right] <= x)
return right;
if (arr[left] > x)
return left;
int mid = (left + right)/2;
if(arr[mid] <= x && arr[mid+1] > x)
return mid;
if(arr[mid] < x)
return getCrossoverPoint(arr, mid+1, right, x);
return getCrossoverPoint(arr, left, mid - 1, x);
}
void findKClosestNumbers(int arr[], int x, int k, int n) {
int l = getCrossoverPoint(arr, 0, n-1, x);
int r = l+1;
int count = 0;
if (arr[l] == x) l--;
while (l >= 0 && r < n && count < k) {
if (x - arr[l] < arr[r] - x)
cout << arr[l--] << " ";
else
cout << arr[r++] << " ";
count++;
}
while (count < k && l >= 0){
cout << arr[l--] << " ";
count++;
}
while (count < k && r < n){
cout << arr[r++] << " ";
count++;
}
}
int main() {
int arr[] ={12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 35, k = 5;
findKClosestNumbers(arr, x, k, n);
} Đầu ra
39 30 42 45 48