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」になります。

解法の考え方：二分探索を活用する

この問題を効率的に解くには、二分探索（バイナリサーチ）の手法を利用します。二分探索によって「クロスオーバーポイント（X 以下の要素と X より大きい要素の境界となる位置）」を求めます。この境界位置さえ特定できれば、そこから左右へ同時にポインタを広げていくことで、O(k) の時間計算量で k 個の近接要素を出力できます。

アルゴリズムの流れ

1. クロスオーバーポイントの探索： 二分探索を使い、X 以下で最大の要素のインデックスを求めます。
2. 左右ポインタの設定： 見つかった位置を l、その右隣を r とします。もし arr[l] == x であれば、X 自身は出力対象外のため、l を1つ左へずらします。
3. 距離の比較： x - arr[l] と arr[r] - x を比較し、より近い方の要素を出力して、その側のポインタを移動させます。
4. 残りの補完処理： 片側の要素が尽きた場合は、もう片側から順番に必要な数だけ出力します。

C++での実装例

#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

上記のコードでは x = 35、k = 5 として実行しているため、出力は5つの要素になっています。X = 35 は配列内に存在するため出力から除外され、それ以外の要素が X との距離が近い順に表示されていることが確認できます。

計算量について

• 時間計算量： 二分探索によるクロスオーバーポイントの探索に O(log n)、近接要素の出力に O(k)。全体としては非常に効率的です。
• 空間計算量： O(1)。追加の配列などは不要で、ポインタ変数のみで処理できます。