C++でソート済み配列内の「指定値より小さい要素」を効率的にカウントする方法

はじめに

この記事では、C++を使ってソート済み配列の中から、指定した数値より小さい要素の個数をカウントするプログラムについて解説します。

具体的には、ある数値 x が与えられたとき、昇順にソートされた配列の中に存在する「x より小さい要素」がいくつあるかを求めるのが目的です。

解決のアプローチ：upper_bound を活用する

配列がすでにソートされているため、先頭から順に比較していく線形探索（計算量 O(n)）は不要です。標準ライブラリの upper_bound 関数を使えば、二分探索（計算量 O(log n)）で効率的に答えを求めることができます。

upper_bound(first, last, x) は、ソート済みの範囲内で「x より大きい要素が最初に現れる位置」へのイテレータを返します。この戻り値から配列の先頭アドレスを引くことで、その位置までの要素数＝指定値以下の要素の個数が一発で求まります。

サンプルコード

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

int countSmaller(int arr[], int n, int x){
    return upper_bound(arr, arr + n, x) - arr;
}

int main(){
    int arr[] = { 10, 20, 30, 40, 50 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << countSmaller(arr, n, 45) << endl;
    cout << countSmaller(arr, n, 55) << endl;
    cout << countSmaller(arr, n, 4) << endl;
    return 0;
}

実行結果

4
5
0

実行結果の解説

• x = 45 の場合： 45 未満の要素は 10, 20, 30, 40 の 4 つなので、出力は 4。
• x = 55 の場合： 配列内のすべての要素（10〜50）が 55 未満なので、出力は 5。
• x = 4 の場合： 4 未満の要素は 1 つも存在しないため、出力は 0。

重複要素がある場合の注意点

upper_bound は「x より大きい要素の先頭位置」を返すため、配列内に x と等しい値が含まれている場合、それらもカウントに含まれてしまいます。厳密に「x 未満」の要素だけを数えたい場合は、代わりに lower_bound を使用してください。

// x 未満の要素のみを厳密にカウントする場合
return lower_bound(arr, arr + n, x) - arr;

まとめ

ソート済み配列に対しては upper_bound（または lower_bound）による二分探索を利用することで、指定値より小さい要素の個数をわずか O(log n) の計算量で高速に求められます。要素数が多いデータセットを扱う際に特に有効なテクニックなので、ぜひ活用してみてください。