Namaran

Code daily. Without assist.

2026-08-29

lower_bound.rs

fn lower_bound(v: &[i32], target: i32) -> usize {
    let (mut lo, mut hi) = (0, v.len());
    while lo < hi {
        let mid = (lo + hi) / 2;
        if v[mid] < target {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    lo
}

fn main() {
    println!("{}", lower_bound(&[1, 3, 5, 7], 4));
}

小さい順に並んだスライス v の中で、target 以上の値が最初に現れる位置を返す lower_bound です。lower_bound(&[1, 3, 5, 7], 4) は本来 2 を返すはずが、いまは呼び出しから返ってこず、何も出力されないまま動き続けます。

Answer

Wrong

if v[mid] < target {
    lo = mid;
} else {

このループが止まるには、範囲の幅 hi - lo が1回ごとに真に減らなければなりません。hi = mid の側は、mid が常に hi より小さいので幅が必ず減ります。一方 (lo + hi) / 2 は切り捨てなので、幅が1のとき mid は lo と等しくなり、lo = mid では範囲が変わりません。

入力例では、(0, 4) から mid = 2 の 5 を見て (0, 2) になり、mid = 1 の 3 を見て lo = 1 で (1, 2) になります。次の mid は (1 + 2) / 2 で再び1になり、3 < 4 なので lo にまた1が入って、同じ状態が限りなく続きます。

Right

if v[mid] < target {
    lo = mid + 1;
} else {

v[mid] < target なら mid の位置は答えになりえないので、範囲から外して mid + 1 から探せば足ります。mid は lo 以上なので lo は必ず1以上増え、どちらの枝でも幅が真に減ります。入力例では (1, 2) から lo = 2 となって lo < hi が偽になり、2 を返します。