lower_bound(), upper_bound()の練習帳

事前準備

数列は昇順にソートされている必要があります。

#include <iostream>
#include <algorithm>

int main() {
    std::vector<int> nums{1,1,1,1,2,2,3,3,3,4,4,6,6,6};
    std::sort(nums.begin(), nums.end());
    ....
}

要素の数を数える

「3より小さい要素数」「3以下の要素数」を数える方法は以下のとおりです。

// 3より小さい要素の数
int lessThan3 = std::lower_bound(nums.begin(), nums.end(), 3) - nums.begin();
std::cout << lessThan3 << std::endl;  // 6

// 3以下の要素の数
int equalOrLessThan3 = std::upper_bound(nums.begin(), nums.end(), 3) - nums.begin();
std::cout << equalOrLessThan3 << std::endl;  // 9

「3より大きい要素数」「3以上の要素数」を数える方法は以下のとおりです。

// 3より大きい要素の数 (= 全要素数 - 3以下の要素数)
int equalOrMoreThan3 = nums.end() - std::upper_bound(nums.begin(), nums.end(), 3);
std::cout << equalOrMoreThan3 << std::endl;  // 8

// 3以上の要素の数 (= 全要素数 - 3未満の要素数)
int moreThan3 = nums.end() - std::lower_bound(nums.begin(), nums.end(), 3);
std::cout << moreThan3 << std::endl;  // 5

別解として、引き算を使っても求められます。

// 3より大きい要素の数 (= 全要素数 - 3以下の要素数)
int moreThan3 = nums.size() - equalOrLessThan3;
std::cout << moreThan3 << std::endl;  // 5

// 3以上の要素の数 (= 全要素数 - 3未満の要素数)
int equalOrMoreThan3 = nums.size() - lessThan3;
std::cout << equalOrMoreThan3 << std::endl;  // 8

<!-- 関数化しておくと便利です。

#include <iostream>
#include <algorithm>

// n未満の要素数を求める (numsはソート済とする)
template <typename T>
T get_less_than_n(std::vector<T>& nums, T n) {
    return std::lower_bound(nums.begin(), nums.end(), n) - nums.begin();
}

// n以下の要素数を求める (numsはソート済とする)
template <typename T>
T get_equal_or_less_than_n(std::vector<T>& nums, T n) {
    return std::upper_bound(nums.begin(), nums.end(), n) - nums.begin();
}

// nより大きい要素数を求める (numsはソート済とする)
template <typename T>
T get_more_than_n(std::vector<T>& nums, T n) {
    return nums.end() - std::lower_bound(nums.begin(), nums.end(), n);
}

// n以上の要素数を求める (numsはソート済とする)
template <typename T>
T get_equal_or_more_than_n(std::vector<T>& nums, T n) {
    return nums.end() - std::upper_bound(nums.begin(), nums.end(), n);
}
-->

int main() {
    std::vector<int> nums{1,1,1,1,2,2,3,3,3,4,4,6,6,6};
    std::sort(nums.begin(), nums.end());

    std::cout << get_less_than_n(nums, 3) << std::endl;
    std::cout << get_equal_or_less_than_n(nums, 3) << std::endl;
    std::cout << get_more_than_n(nums, 3) << std::endl;
    std::cout << get_equal_or_more_than_n(nums, 3) << std::endl;

    return 0;
}