C++で二分探索で配列の中の条件を満たす要素の数を求める

１点

xより大きい要素の数

return distance(upper_bound(begin, end, x), end);

xと等しい要素の数

auto er = equal_range(begin, end, r);
return distance(er.first, er.second);

xより小さい

return distance(begin, lower_bound(begin, end, x));

区間

xより大きくyより小さい

if(x > y) return 0;
if(begin >= end) return 0;
return distance(upper_bound(begin, end, left), lower_bound(begin, end, right));

ライブラリ化

struct RangeCount {
    int upper, r_equal, between, l_equal, lower;

    friend std::ostream &operator<<(std::ostream &out, const RangeCount &o) {
        cout << endl;
        cout << "upper" << ' ' << o.upper << endl;
        cout << "r_equal" << ' ' << o.r_equal << endl;
        cout << "between" << ' ' << o.between << endl;
        cout << "l_equal" << ' ' << o.l_equal << endl;
        cout << "lower" << ' ' << o.lower << endl;
        return out;
    }
};


// startは含む
// endは含まない
RangeCount range_count(vector<int>::iterator begin, vector<int>::iterator end, int l, int r) {
    if (l > r) return RangeCount{0, 0, 0, 0, 0};
    if (begin >= end) return RangeCount{0, 0, 0, 0, 0};

    if (l == r) {
        RangeCount rc;
        auto it = std::equal_range(begin, end, r);

        rc.upper = distance(it.second, end);
        rc.r_equal = distance(it.first, it.second);
        rc.between = 0;
        rc.l_equal = rc.r_equal;
        rc.lower = distance(begin, it.first);

        return rc;
    }

    RangeCount rc;
    auto it_r = std::equal_range(begin, end, r);
    auto it_l = std::equal_range(begin, end, l);

    auto it_ru = it_r.second;
    auto it_rl = it_r.first;
    rc.upper = distance(it_ru, end);
    rc.r_equal = distance(it_rl, it_ru);
    auto it_lu = it_l.second;
    auto it_ll = it_l.first;
    rc.between = distance(it_lu, it_rl);
    rc.l_equal = distance(it_ll, it_lu);
    rc.lower = distance(begin, it_ll);

    return rc;

}

使い方

左右の境界値を含めるかどうかは
betweenにl_equalとr_equalを足すかどうかで選べます。

// left <= x < rightだったら
RangeCount rc = range_count(left, right);
return  rc.l_equal + rc.between;

注意点として、left <= x <= rightを求めたい時に
rc.l_equal + rc.between + rc.r_equal と書きたくなりますが、
left == rightだったらバグるので、その分岐が必要です。