2026-09-29
lower_bound_index.cpp
#include <cstddef>
#include <vector>
std::size_t lower_bound_index(const std::vector<int>& v, int x) {
}
昇順に並んだ v の中で、x 以上の値が最初に現れる位置を返す lower_bound_index を書いてください。x 以上の値がひとつもなければ v.size() を返します。v が空なら 0 です。
入力例 1
lower_bound_index({1, 3, 3, 7}, 3)
出力例 1
1
入力例 2
lower_bound_index({1, 3, 3, 7}, 8)
出力例 2
4
入力例 3
lower_bound_index({}, 5)
出力例 3
0
Reference
std::size_t lower_bound_index(const std::vector<int>& v, int x) {
std::size_t lo = 0;
std::size_t hi = v.size();
while (lo < hi) {
std::size_t mid = lo + (hi - lo) / 2;
if (v[mid] < x) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
答えがありうる範囲を半開区間 [lo, hi) で持ち、1回ごとに必ず狭めます。v[mid] < x なら mid 自身も答えではないので lo = mid + 1 とし、そうでなければ mid が答えの候補として残るので hi = mid とします。mid は lo 以上 hi 未満なので、どちらの更新でも区間は1つ以上縮み、lo == hi になったところでループが終わります。
止まらなくなる典型は、lo = mid と書くことです。区間の幅が1のときは mid が lo と等しいので、lo = mid では区間が変わらず、同じ mid を調べ続けます。hi を閉区間の端として持つ while (lo <= hi) の書き方もありますが、hi = mid - 1 で mid が 0 のとき、std::size_t の引き算が最大値に回り込みます。
mid を (lo + hi) / 2 ではなく lo + (hi - lo) / 2 で求めるのは、足し算のあふれを避けるためです。掲載したのは参考実装で、唯一の正解ではありません。実務では std::lower_bound(v.begin(), v.end(), x) - v.begin() で同じ値が得られます。