lower_bound・upper_bound

ソート済み配列に対して、条件を満たす位置や要素数を二分探索で求める。

特徴

項目	内容
用途	境界位置の取得・条件を満たす要素数
計算量	O(log N)
前提	検索対象の範囲が昇順にソートされている

実装

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

template <class T>
struct SortedRange {
    const vector<T>& a;
    int l, r;

    SortedRange(const vector<T>& a, int l, int r) : a(a), l(l), r(r) {
        assert(0 <= l && l <= r && r <= (int)a.size());
    }
    SortedRange(const vector<T>& a) : SortedRange(a, 0, (int)a.size()) {}

    // 元の配列における添え字を返す（見つからなければr）
    template <class X>
    int first_ge(const X& x) const { return lower_bound(a.begin() + l, a.begin() + r, x) - a.begin(); }
    template <class X>
    int first_gt(const X& x) const { return upper_bound(a.begin() + l, a.begin() + r, x) - a.begin(); }

    // 条件を満たす要素数
    template <class X>
    int count_lt(const X& x) const { return first_ge(x) - l; }
    template <class X>
    int count_le(const X& x) const { return first_gt(x) - l; }
    template <class X>
    int count_ge(const X& x) const { return r - first_ge(x); }
    template <class X>
    int count_gt(const X& x) const { return r - first_gt(x); }

    // 値の区間で数える
    template <class X, class Y>
    int count_open(const X& lo, const Y& hi) const { return max(0, first_ge(hi) - first_gt(lo)); }
    template <class X, class Y>
    int count_closed(const X& lo, const Y& hi) const { return max(0, first_gt(hi) - first_ge(lo)); }
    template <class X, class Y>
    int count_half_open(const X& lo, const Y& hi) const { return max(0, first_ge(hi) - first_ge(lo)); }
};

境界位置

• first_ge(x)：最初のx以上
• first_gt(x)：最初のx超過

位置が存在しない場合は、検索範囲の終端を返す。

個数の取得

SortedRange(a).count_lt(x);           // x未満
SortedRange(a).count_le(x);           // x以下
SortedRange(a).count_ge(x);           // x以上
SortedRange(a).count_gt(x);           // x超過

SortedRange(a).count_open(l, r);      // l < x < r
SortedRange(a).count_closed(l, r);    // l <= x <= r
SortedRange(a).count_half_open(l, r); // l <= x < r

添え字の範囲指定

SortedRange(a, 0, j).count_ge(x);

配列の [0, j) だけを検索する。

添え字の範囲は常に半開区間 [l, r)。

注意点

• 検索対象は昇順ソート済みであること。
• 添え字と要素数を混同しない。
• first_ge / first_gt は元配列での添え字を返す。
• 見つからない場合、検索範囲の終端 r を返す。
• 存在しない位置の要素を参照しない。
• 整数の厳密不等号には、x+1 を使うより upper_bound が安全。
• 条件を満たす要素数だけ必要なら、count_* を利用する。