C++でソート済み配列から「kより大きい要素」の個数を求める方法

この問題では、N個のソート済み整数からなる配列 arr[] と整数 k が与えられます。目的は、配列内で k より大きい要素の個数を求めることです。

問題例

入力

arr[] = {1, 2, 5, 7, 8, 9}、k = 4

出力

4

説明

k = 4 より大きい要素は
5, 7, 8, 9 の4つ

解法1：線形探索（シンプルな方法）

最も単純な解法は、配列の先頭から末尾までループで走査し、k より大きい最初の要素が見つかった時点で処理を止める方法です。その位置以降に残っている要素の数が、求める個数となります。

実装例

#include <iostream>
using namespace std;
int findGreaterCount(int arr[], int n, int k){
    for(int i = 0; i < n; i++){
        if(arr[i] > k)
            return (n - i);
    }
    return -1;
}
int main(){
    int arr[] = { 1, 3, 5, 7, 7, 8, 12, 21};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    cout<<"The number of elements greater than k is "<<findGreaterCount(arr, n, k);
    return 0;
}

出力

The number of elements greater than k is 5

このコードは正しく動作しますが、計算量は O(N) となり、配列サイズが大きい場合には非効率です。

解法2：二分探索（効率的な方法）

配列がすでにソートされていることを活かせば、二分探索を使って k より大きい要素の中で最小の位置（境界）を O(log N) で見つけられます。見つかった位置から配列末尾までの要素数が答えになります。

アルゴリズムの流れ

探索範囲の中央値が k より大きければ、その位置を候補として記録し、左半分をさらに探索します。k 以下であれば右半分へ移動します。これを繰り返すことで、k を超える要素が最初に現れるインデックスを特定できます。

実装例

#include <iostream>
using namespace std;
int findGreaterCount(int arr[], int n, int k){
    int s = 0;
    int e = n - 1;
    int firstGreterEle = n;
    while (s <= e) {
        int mid = s + (e - s) / 2;
        if (arr[mid] > k) {
            firstGreterEle = mid;
            e = mid - 1;
        }
        else
            s = mid + 1;
    }
    return (n - firstGreterEle);
}
int main(){
    int arr[] = { 1, 3, 5, 7, 7, 8, 12, 21};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    cout<<"The number of elements greater than k is "<<findGreaterCount(arr, n, k);
    return 0;
}

出力

The number of elements greater than k is 5

まとめ

ソート済み配列が前提となるこの問題では、二分探索を用いることで大幅な高速化が期待できます。同様の考え方は、C++標準ライブラリの std::upper_bound でも実現できるため、実務ではこちらを活用するのも有効です。