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입니다.

해결 접근 방식: 이진 탐색 활용

이 문제는 이진 탐색(Binary Search)을 활용하면 효율적으로 해결할 수 있습니다. 먼저 이진 탐색으로 '크로스오버 지점(crossover point)', 즉 X보다 작거나 같은 값을 가진 마지막 요소의 인덱스를 찾습니다. 크로스오버 지점만 확인되면, 그 지점을 중심으로 왼쪽과 오른쪽을 번갈아 비교하면서 더 가까운 요소부터 차례로 선택하는 방식으로 k개의 최근접 요소를 O(k) 시간에 출력할 수 있습니다.

알고리즘 동작 단계

1. 이진 탐색으로 크로스오버 지점을 찾습니다.
2. 크로스오버 지점을 l로, 바로 다음 인덱스를 r로 설정합니다.
3. 만약 arr[l] == x라면 X 자체는 결과에서 제외해야 하므로 l을 한 칸 왼쪽으로 옮깁니다.
4. (x - arr[l])과 (arr[r] - x)를 비교하여 더 가까운 쪽의 요소를 출력하고 해당 포인터를 이동시킵니다.
5. 어느 한쪽이 배열의 경계를 벗어나면, 남은 쪽의 요소들을 순서대로 출력합니다.

크로스오버 지점을 찾는 데 O(log n), k개의 요소를 고르는 데 O(k)가 소요되므로 전체 시간 복잡도는 O(log n + k)입니다. 이는 모든 요소의 거리를 계산한 뒤 정렬하는 O(n log n) 방식보다 훨씬 효율적입니다.

C++ 구현 코드

#include<iostream>
using namespace std;

// 이진 탐색으로 크로스오버 지점(x보다 작거나 같은 마지막 요소의 인덱스)을 찾는 함수
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);
}

// X에 가장 가까운 k개의 요소를 출력하는 함수
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--;   // X가 배열에 존재하면 결과에서 제외
    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

예제에서는 X = 35, k = 5로 실행했습니다. 35는 배열에 실제로 존재하기 때문에 결과에서 제외되며, 거리가 가까운 순서대로 39(거리 4), 30(거리 5), 42(거리 7), 45(거리 10), 48(거리 13)이 출력됩니다. 참고로 출력은 거리 우선 순서이므로, 값의 오름차순 정렬이 필요하다면 결과를 별도로 정렬하면 됩니다.