Namaran

Code daily. Without assist.

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回の呼び出しで受け取れます。掲載したのは参考実装で、唯一の正解ではありません。