【C++】ソート済み配列からフロア（x以下の最大要素）を効率的に求める方法

この記事では、ソート済み配列 arr[] と整数値 x が与えられたときに、配列内の「フロア（floor）」を見つけるプログラムをC++で作成する方法を解説します。

フロアとは？

ソート済み配列 arr における x のフロアとは、配列 arr[] の要素の中で、x 以下である最大の要素のことです。

具体例で問題を理解しよう

入力：arr[] = {2, 5, 6, 8, 9, 12, 21, 25}, x = 10
出力：9

説明： 上記の配列において、10 以下である最大の数は 9 です。したがって答えは 9 となります。

解法1：線形探索によるシンプルなアプローチ

最も簡単な解決策は、配列を先頭から順に走査し、条件を満たす要素を見つける方法です。配列を走査しながら各要素をチェックし、x より大きい要素が見つかった時点で、その直前の要素を x のフロアとして返します。

実装例

この解法の動作を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;

int findFloorSortedArray(int arr[], int n, int x){
    if (x >= arr[n - 1])
        return (n-1);
    if (x < arr[0])
        return -1;
    for (int i = 1; i < n; i++)
        if (arr[i] > x)
            return (i - 1);
    return -1;
}
int main(){
    int arr[] = {2, 5, 6, 8, 9, 12, 21, 25};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int floorIndex = findFloorSortedArray(arr, n - 1, x);
    if (floorIndex == -1)
        cout<<"The floor of "<<x<<" doesn't exist in the array";
    else
        cout<<"The floor of "<<x<<" in the array is "<<arr[floorIndex];
    return 0;
}

出力結果

The floor of 10 in the array is 9

この方法の計算量は O(n) となり、配列のサイズが大きい場合は非効率になる可能性があります。

解法2：二分探索による効率的なアプローチ

より効率的な解法として、二分探索アルゴリズムを利用する方法があります。配列がソート済みであり、目的が値の検索であるため、二分探索が適しています。

この解法では、まず配列の中央インデックスにある要素を調べます。そして中央の要素との大小関係に応じて、配列の前半（小さい側）または後半（大きい側）のどちらか一方だけをさらに探索します。この処理を、サブ配列の中央で目的の要素が見つかるまで繰り返します。

これにより計算量を O(log n) に抑えることができ、大きな配列でも高速にフロアを求められます。

実装例

この解法の動作を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;

int findFloorSortedArray(int arr[], int start, int end, int x){
    if (start > end)
        return -1;
    if (x >= arr[end])
        return end;
    int mid = (start + end) / 2;
    if (arr[mid] == x)
        return mid;
    if (mid > 0 && arr[mid - 1] <= x && x < arr[mid])
        return mid - 1;
    if (x < arr[mid])
        return findFloorSortedArray(arr, start, mid - 1, x);
    return findFloorSortedArray(arr, mid + 1, end, x);
}
int main(){
    int arr[] = {2, 5, 6, 8, 9, 12, 21, 25};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int floorIndex = findFloorSortedArray(arr, 0, n - 1, x);
    if (floorIndex == -1)
        cout<<"The floor of "<<x<<" doesn't exist in the array";
    else
        cout<<"The floor of "<<x<<" in the array is "<<arr[floorIndex];
    return 0;
}

出力結果

The floor of 10 in the array is 9

まとめ

ソート済み配列から x のフロアを求めるには、線形探索でも実装できますが、配列がソートされているという性質を活かせば、二分探索を使うことで O(log n) の高速な処理が可能になります。データ量が多い場面では、二分探索版の実装を選ぶことをおすすめします。