c++ - ソートされた範囲内の要素の数を見つける最速の方法は何ですか?

Question

ソートされたリストが与えられた場合、すべての数値が整数であると仮定して、指定された範囲内の要素の数をカウントする
1, 3, 5, 6, 9....
よりも高速なアルゴリズムはありますか?O(n)[a, b]

Answer 1

lower_boundupper_boundソートされたコンテナで動作します。

最初に範囲内の下限値を見つけ、そこから上限値を最後まで検索します。関数の実装では、おそらく二分探索を使用します。

#include <algorithm>
#include <list>
#include <iterator>

int main() {
    using std::list;
    using std::upper_bound;
    using std::lower_bound;
    using std::distance;

    list<int> numbers = {1, 3, 5, 6, 9};
    int a = 3;
    int b = 6;

    auto lower = lower_bound(numbers.begin(), numbers.end(),
                             a);
    auto upper = upper_bound(lower, numbers.end(),
                             b);

    int count = distance(lower, upper);

    return 0;
}