C++에서 주어진 값에 가장 가까운 k개의 요소 찾기

요소가 거의 없는 배열 A가 있다고 가정합니다. 두 개의 다른 값 X와 k가 있습니다. 우리의 임무는 배열 A에서 X의 가장 가까운 요소의 k개를 찾는 것입니다. 요소 X가 배열에 있으면 출력에 표시되지 않습니다. A =[12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56]이고 X =35, k =4인 경우 출력은 30, 39, 42, 45입니다. .

이를 해결하기 위해 이진 검색 접근 방식을 사용합니다. 이것을 사용하여 우리는 교차점을 얻을 것입니다. 교차점의 인덱스가 발견되면 O(k) 시간에 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