2026-10-15
positions.cpp
#include <utility>
#include <vector>
std::pair<int, int> positions(const std::vector<int>& v, int x) {
}
昇順に並んだ v の中で x と等しい要素が並ぶ範囲を、最初の添字と最後の添字の組で返す positions を書いてください。x が v に無いときは {-1, -1} を返します。v の要素数を n として、比較の回数は O(log n) に収めます。
入力例 1
positions({1, 2, 2, 2, 5}, 2)
出力例 1
{1, 3}
入力例 2
positions({1, 2, 2, 2, 5}, 3)
出力例 2
{-1, -1}
入力例 3
positions({4}, 4)
出力例 3
{0, 0}
Reference
std::pair<int, int> positions(const std::vector<int>& v, int x) {
auto lo = std::lower_bound(v.begin(), v.end(), x);
auto hi = std::upper_bound(lo, v.end(), x);
if (lo == hi) {
return {-1, -1};
}
return {static_cast<int>(lo - v.begin()), static_cast<int>(hi - v.begin()) - 1};
}
lower_bound は x 以上の最初の要素を、upper_bound は x より大きい最初の要素を指します。x と等しい要素はこの2つの間の半開区間 [lo, hi) に並び、hi は最後の x の1つ後を指すので、最後の添字は hi - v.begin() から1を引いた値です。
x が無いと lo と hi は同じ位置になり、そこから1を引くと x と関係のない要素の添字が返ってしまいます。そのため先に lo == hi を調べて {-1, -1} を返しています。upper_bound の探索を lo から始めているのは、x より大きい要素が lo より前に無いからです。
添字は int で返すので、イテレータの差を static_cast で変換しています。std::equal_range を使えば、lo と hi を1回の呼び出しで受け取れます。掲載したのは参考実装で、唯一の正解ではありません。