พิจารณาว่าเรามีอาร์เรย์ A ที่มีสมาชิกบางส่วน เรามีค่า X และ k อีกสองค่า งานของเราคือหา k จำนวนสมาชิกที่ใกล้เคียง X มากที่สุดจากอาร์เรย์ A ถ้าสมาชิก X อยู่ในอาร์เรย์ จะไม่แสดงในเอาต์พุท ถ้า A = [12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56] และ X = 35, k = 4 เอาต์พุทจะเป็น 30, 39, 42, 45
เพื่อแก้ปัญหานี้ เราจะใช้วิธีการค้นหาแบบทวิภาค (binary search) ด้วยวิธีนี้เราจะได้จุดข้าม (crossover point) ถ้าดัชนีของจุดข้ามพบแล้ว เราสามารถพิมพ์ k ตัวเลขที่ใกล้ที่สุดได้ในเวลา O(k)
ตัวอย่าง
#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);
}
ผลลัพธ์
39 30 42 45 48
