C++でソート済み配列からK以下の要素数を数える方法（線形探索・二分探索）

ソート済みの整数配列が与えられたとき、「指定した値 K 以下の要素がいくつあるか」を求めるのがこの問題の目的です。ここでは、線形探索による素朴な方法と、二分探索を使った効率的な方法の2通りを解説します。

問題の例

入力

Arr[]= { 1, 2, 3, 14, 50, 69, 90 }　K = 12

出力

K以下の要素数: 3

説明

1, 2, 3 の3つが 12 以下です。

入力

Arr[]= { 12, 13, 13, 13, 14, 50, 54, 100 }　K = 14

出力

K以下の要素数: 5

説明

12, 13, 13, 13, 14 の5つが 14 以下です。

方法1：線形探索（素朴なアプローチ）

アルゴリズムの流れ

• 整数配列 Arr[] と値 K を受け取ります。
• 関数 smallorEqual(int arr[], int k, int len) は、arr[] 内の K 以下の要素数を返します。
• カウンタ変数 count を 0 で初期化します。
• for ループで i = 0 から i < len まで配列を先頭から順に走査します。
• 各要素 arr[i] が K 以下であれば count を +1 します。配列はソート済みなので、K より大きい要素が出現した時点で break してループを抜けて構いません。
• ループ終了後の count が条件を満たす要素の総数になります。
• count を結果として返します。

この方法の計算量は O(n) です。

実装例

#include <bits/stdc++.h>
using namespace std;

int smallorEqual(int arr[], int k, int len){
    int count = 0;
    for (int i = 0; i < len; i++){
        if(arr[i] <= k)
            { count++; }
        else
            { break; }   // ソート済みなので、Kを超えたら以降は見る必要なし
    }
    return count;
}

int main(){
    int Arr[] = { 1,5,11,12,19,21,32,53,70,100 };
    int K = 21;
    int Length = sizeof(Arr)/sizeof(Arr[0]);
    cout << "K以下の要素数: " << smallorEqual(Arr, K, Length);
    return 0;
}

実行結果

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

K以下の要素数: 6

方法2：二分探索を使った効率的なアプローチ

配列がソート済みであることを活かせば、二分探索によって計算量を O(log n) まで削減できます。求めるべきは「K 以下の要素がどこまで続くか」、つまり「K 以下の要素のうち最も右側にあるインデックス」です。

アルゴリズムの流れ

• 整数配列 Arr[] と値 K を受け取ります。
• 関数 binarySearch(int arr[], int k, int len) は、arr[] 内の K 以下の要素数を返します。
• low = 0、high = len - 1 とし、mid = (low + high) / 2 を計算します。
• index を -1 で初期化します（K 以下の要素が1つも存在しない場合に備えます）。
• while ループで low <= high の間、以下を繰り返します。
• arr[mid] <= k ならば、index = mid として答えの候補を更新し、low = mid + 1 として右半分をさらに探索します。
• そうでなければ high = mid - 1 として左半分を探索します。
• ループ終了時、index には「K 以下の要素のうち最も右側のインデックス」が入ります。
• index + 1 を返します。配列のインデックスは0始まりなので、0 ～ index までの要素がすべて K 以下であるためです。

実装例

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int k, int len){
    int low = 0;
    int high = len - 1;
    int mid = (high + low) / 2;
    int index = -1;

    while(low <= high){
        mid = (low + high) / 2;
        if(arr[mid] <= k){
            index = mid;      // 答えの候補を更新
            low = mid + 1;    // さらに右側を探す
        }
        else{
            high = mid - 1;   // 左側を探す
        }
    }
    return (index + 1);
}

int main(){
    int Arr[] = { 1,5,11,12,19,21,32,53,70,100 };
    int K = 21;
    int Length = sizeof(Arr)/sizeof(Arr[0]);
    cout << "K以下の要素数: " << binarySearch(Arr, K, Length);
    return 0;
}

実行結果

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

K以下の要素数: 6

2つの手法の比較

• 線形探索： 実装がシンプルで、配列がソートされていなくても利用できます。計算量は O(n)。
• 二分探索： 配列がソート済みであることが前提ですが、計算量は O(log n)。データ件数が多い場合ほど高速さが際立ちます。

また、C++ の標準ライブラリには std::upper_bound が用意されており、これを使えば同じ処理を1行で実現できます。upper_bound(Arr, Arr + Length, K) - Arr は「K より大きい最初の要素の位置」を返すため、その差がそのまま K 以下の要素数になります。実務では、この標準関数を活用するのが最も簡潔で安全な選択肢といえるでしょう。