2026-10-15
bounds.cpp
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {1, 3, 3, 3, 7};
for (int x : {3, 5}) {
auto lo = std::lower_bound(v.begin(), v.end(), x);
auto hi = std::upper_bound(v.begin(), v.end(), x);
std::cout << lo - v.begin() << ' ' << hi - v.begin() << '\n';
}
}
これは何を出力するでしょうか?
Answer
1 4 と 4 4 の2行です。
lower_bound は x 以上になる最初の要素を、upper_bound は x より大きくなる最初の要素を指します。x = 3 なら、3 以上の最初は添字1の 3、3 より大きい最初は添字4の 7 です。upper_bound が指すのは最後の 3(添字3)ではなくその次の要素なので、2つの位置は 3 が並ぶ範囲を、終わりを含まない半開区間 [1, 4) で表します。3 の個数は差の 4 - 1 = 3 です。
x = 5 は v にありません。それでも end()(添字5)が返るわけではなく、5 以上の最初も 5 より大きい最初も添字4の 7 なので、どちらも 4 になります。この位置は、5 を挿入しても昇順が崩れない場所です。2つの位置が等しいことが、5 と等しい要素が1つも無いことを表しています。