C++で部分配列内の指定した数以下の要素を数える方法

問題の概要

配列と、部分配列の下限インデックス（lower）および上限インデックス（upper）、さらに基準となる数値 k が与えられます。このとき、指定された範囲内に存在する「k 以下の要素」がいくつあるかを数えるのが目的です。

具体的な例を見てみましょう。

入力

arr = [1, 2, 3, 4, 5, 6, 7, 8]
k = 4
lower = 0
upper = 5

出力

4

この場合、インデックス 0 から 5 の間には「4 以下の要素」が 1, 2, 3, 4 の 4 つ存在するため、答えは 4 となります。

アルゴリズム

• 配列、基準となる数値、部分配列のインデックスを初期化します。

• カウント用の変数を 0 で初期化します。

• 部分配列の下限インデックスから上限インデックスまで順に走査するループを作成します。

  • 現在の要素が指定された数値以下であれば、カウントを 1 増やします。

• 最後にカウントを返します。

この手法は線形探索であり、計算量は範囲のサイズに対して O(n) です。範囲の妥当性チェック（lower が負でないこと、upper が配列の範囲内であることなど）を行うことで、不正な入力にも安全に対応できます。

C++での実装

上記のアルゴリズムを C++ で実装すると、次のようになります。

#include <bits/stdc++.h>
using namespace std;
int getElementsCount(int arr[], int n, int lower, int upper, int k) {
    if (lower < 0 || upper >= n || lower > upper) {
        return 0;
    }
    int count = 0;
    for (int i = lower; i <= upper; i++) {
        if (arr[i] <= k) {
            count += 1;
        }
    }
    return count;
}
int main() {
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
    int n = 8, k = 4;
    cout << getElementsCount(arr, n, 0, 3, k) << endl;
    cout << getElementsCount(arr, n, 4, 7, k) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

4
0

最初の呼び出しでは、インデックス 0 ～ 3 の範囲（1, 2, 3, 4）に 4 以下の要素が 4 つあるため「4」が出力されます。一方、2 回目の呼び出しでは、インデックス 4 ～ 7 の範囲（5, 6, 7, 8）に 4 以下の要素は存在しないため「0」となります。