Namaran

Code daily. Without assist.

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() で同じ値が得られます。