C++で解く「以上」と「より大きい」のクエリ処理：二分探索による効率化

問題概要

本記事で扱うのは、配列が与えられたときに次の2種類のクエリに答える問題です。

• タイプ0 ― x（指定された値）以上の要素がいくつあるかを求める。
• タイプ1 ― xより大きい要素がいくつあるかを求める。

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

入力 : arr[] = { 10, 15, 30, 40, 45 }、Q = 3
    クエリ1 : 0 50
    クエリ2 : 1 40
    クエリ3 : 0 30
出力 :
    0
    1
    3
説明 :
x = 50, q = 0 : 50以上の要素は存在しない。
x = 40, q = 1 : 45 が 40 より大きい。
x = 30, q = 0 : 30, 40, 45 の3要素が 30 以上である。

解法のアプローチ

解法には主に2つの方法があります。まず単純な全探索（ブルートフォース）を実装し、大きな制約にも耐えられるかを検証します。もし耐えられない場合は、その解法を最適化していく流れです。

アプローチ1：全探索（ブルートフォース）

この方法では、Q個のクエリそれぞれに対して配列を先頭から走査し、条件を満たす要素を数え上げます。

実装例

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

void query(int *arr, int n, int type, int val) {
    int count = 0; // 答え
    if (!type) { // タイプ0のクエリの場合
        for (int i = 0; i < n; i++) {
            if (arr[i] >= val)
                count++;
        }
    } else { // タイプ1のクエリの場合
        for (int i = 0; i < n; i++) {
            if (arr[i] > val)
                count++;
        }
    }
    cout << count << "\n";
}

int main() {
    int ARR[] = { 10, 15, 30, 40, 45 };
    int n = sizeof(ARR)/sizeof(ARR[0]); // 配列のサイズ
    query(ARR, n, 0, 50); // クエリ1
    query(ARR, n, 1, 40); // クエリ2
    query(ARR, n, 0, 30); // クエリ3
    return 0;
}

出力

0
1
3

この方法では単純に配列を走査して各クエリの答えを計算しています。示した例では正しく動作しますが、全体の時間計算量が O(N×Q)（Nは配列のサイズ、Qはクエリの数）となるため、制約が大きいケースでは実行時間内に収まりません。そこで次に、大きな制約にも対応できるようこの解法を最適化します。

アプローチ2：二分探索による効率化

この方法では、二分探索を利用して、指定値の下限（lower_bound：指定値以上が最初に現れる位置）と上限（upper_bound：指定値より大きい値が最初に現れる位置）を求めます。二分探索はソート済み配列でのみ正しく動作するため、あらかじめ配列をソートしておきます。

実装例

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

void lowerbound(int *arr, int n, int val) {
    int l = -1, r = n;
    while (r - l > 1) { // 答えを二分探索
        int mid = (l + r) / 2;
        if (arr[mid] >= val)
            r = mid;
        else
            l = mid;
    }
    if (r == n) // r が動かなければ条件を満たす要素はない
        cout << "0\n";
    else
        cout << n - r << "\n";
}

void upperbound(int *arr, int n, int val) {
    int l = -1, r = n;
    while (r - l > 1) { // 答えを二分探索
        int mid = (l + r) / 2;
        if (arr[mid] > val)
            r = mid;
        else
            l = mid;
    }
    if (r == n) // r が動かなければ条件を満たす要素はない
        cout << "0\n";
    else
        cout << n - r << "\n";
}

void query(int *arr, int n, int type, int val) {
    if (!type) // type == 0 なら lower_bound 関数を呼ぶ
        lowerbound(arr, n, val);
    else // type == 1 なら upper_bound 関数を呼ぶ
        upperbound(arr, n, val);
}

int main() {
    int arr[] = { 1, 2, 3, 4 };
    int n = sizeof(arr)/sizeof(arr[0]); // 配列のサイズ
    sort(arr, arr + n); // 配列をソート
    query(arr, n, 0, 5); // クエリ1
    query(arr, n, 1, 3); // クエリ2
    query(arr, n, 0, 3); // クエリ3
    return 0;
}

出力

0
1
2

このコードでは二分探索を採用することで計算量を大幅に削減しています。ソートに O(N log N)、1回のクエリ回答には O(log N) しかかからないため、クエリが大量にある場合でも高速に処理できます。

コードの解説

このアプローチでは、二分探索によって指定値の lower_bound と upper_bound を求めます。二分探索はソート済みの配列でしか使えないため、まず配列をソートします。自作した lower_bound 関数と upper_bound 関数は、それぞれタイプ0・タイプ1の条件を最初に満たす要素の位置を特定します。配列がソート済みであるため、その位置以降の要素はすべて条件を満たします。つまり、「配列サイズN − 条件を満たす最初のインデックス」がそのまま答えになります。また、探索範囲の右端 r が最後まで動かず n と等しいままの場合は、条件を満たす要素が1つも存在しないため 0 を出力します。

まとめ

本記事では、二分探索を活用して「以上」および「より大きい」のクエリ問題を解きました。全探索という素朴な解法から始めて、その課題を踏まえて二分探索へと改善するまでの過程を、C++のサンプルコードとともに学びました。同じロジックはC言語、Java、Pythonなど他の言語でも同様に実装できます。本記事が読者の皆さんの学習の一助となれば幸いです。