C++でソートされていない配列からフロア値とシーリング値を検索する方法

フロア値とシーリング値とは

この記事では、ソートされていない配列からフロア値(floor)とシーリング値(ceiling)を求める方法を、C++のコード例とともに解説します。

フロア値とは「x以下の要素のうち最大の値」、シーリング値とは「xより大きい要素のうち最小の値」を指します。

たとえば、配列 A = [5, 6, 8, 9, 6, 5, 5, 6]、x = 7 の場合を考えてみましょう。7以下の最大の要素は 6、7より大きい最小の要素は 8 であるため、フロア値は 6、シーリング値は 8 となります。

アルゴリズムの考え方

この問題は、線形探索(リニアサーチ)のアプローチで効率よく解けます。配列を先頭から走査しながら、xとの距離に着目して次の2つの値を追跡します。

• x以上の要素のうち、xとの距離が最小のもの(シーリング候補)
• x以下の要素のうち、xとの距離が最小のもの(フロア候補)
• 走査終了後、それぞれの最小距離に対応する要素を出力する

C++による実装例

#include<iostream>
using namespace std;
void floorCeilingPair(int arr[], int n, int x) {
   int floor_index, ceiling_index;
   int floor_dist = INT_MAX, ceil_dist = INT_MAX;
   for (int i=0; i<n; i++) {
      if (arr[i] >= x && ceil_dist > (arr[i] - x)) {
         ceiling_index = i;
         ceil_dist = arr[i] - x;
      }
      if (arr[i] <= x && floor_dist > (x - arr[i])) {
            floor_index = i;
            floor_dist = x - arr[i];
      }
   }
   if (floor_dist == INT_MAX)
      cout << "フロア値は見つかりません" << endl;
   else
      cout << "フロア値は " << arr[floor_index] << endl;
   if (ceil_dist == INT_MAX)
      cout << "シーリング値は見つかりません" << endl;
   else
      cout << "シーリング値は " << arr[ceiling_index] << endl;
}
int main() {
   int arr[] = {5, 6, 8, 9, 6, 5, 5, 6};
   int n = sizeof(arr)/sizeof(int);
   int x = 7;
   floorCeilingPair(arr, n, x);
}

実行結果

フロア値は 6
シーリング値は 8

コードのポイント

floorCeilingPair 関数では、配列の各要素を1回ずつ確認します。要素がx以上であれば、現在のシーリング候補との距離と比較し、より近い値であれば更新します。同様に、要素がx以下であればフロア候補を更新していきます。

走査が終わった時点で距離が INT_MAX のままの場合は、条件を満たす要素が配列内に存在しないことを意味するため、「見つかりません」というメッセージを出力します。

このアルゴリズムの計算量は O(n) です。配列を1回走査するだけでフロア値とシーリング値の両方を求められるため、シンプルかつ効率的な方法と言えます。