読者です 読者をやめる 読者になる 読者になる

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 moreThan3 = nums.size() - equalOrLessThan3;
std::cout << moreThan3 << std::endl;  // 5

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