Namaran

Code daily. Without assist.

2026-11-18

lower_bound.c

struct entry {
    int year, day;
};

size_t lower(const struct entry* t,
             size_t n,
             int year,
             int day) {
}

配列 t の n 行は、year の昇順に並び、year が同じ行どうしは day の昇順に並んでいます。この順序で引数の (year, day) より前に来ない最初の行の添字を返す lower を書いてください。行 e が (year, day) より前に来るのは、e->year が year より小さいときと、e->year が year と等しく e->day が day より小さいときです。そのような行が無ければ n を返します。比べる回数は、n が2倍になっても1回ほどしか増えないようにしてください。

入力例 1

lower((struct entry[]){{2024, 9}, {2025, 3}, {2025, 8}}, 3, 2025, 5)

出力例 1

2

入力例 2

lower((struct entry[]){{2024, 9}, {2025, 3}, {2025, 8}}, 3, 2025, 3)

出力例 2

1

入力例 3

lower((struct entry[]){{2024, 9}, {2025, 3}}, 2, 2026, 1)

出力例 3

2
Reference

Reference

struct entry {
    int year, day;
};

size_t lower(const struct entry* t,
             size_t n,
             int year,
             int day) {
    size_t lo = 0, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        const struct entry* e = &t[mid];
        if (e->year < year ||
            (e->year == year &&
             e->day < day))
            lo = mid + 1;
        else
            hi = mid;
    }
    return lo;
}

参考実装は、答えが入りうる範囲を半開区間 [lo, hi) で持ち、真ん中の行 e を調べるたびに範囲を半分にします。e が探す値より前に来るなら、答えは e より後ろにあるので lo を mid + 1 に進めます。そうでなければ e 自身が答えの候補なので、hi を mid まで縮めます。範囲が空になったときの lo が答えです。掲載したのは参考実装で、唯一の正解ではありません。

ふつうの二分探索と違うのは、「前に来る」の判定だけです。day を比べるのは year が等しいときに限られます。year が小さい行は day がいくつでも前に来るので、入力例 1 の {2024, 9} は、day の 9 が 5 より大きくても前に来ます。2列を「e->year < year || e->day < day」のように別々に比べると、この行の扱いを誤ります。

入力例 1 では {2025, 3} までが (2025, 5) より前に来るので 2 を返します。入力例 2 では {2025, 3} が探す値と等しく、前に来ない最初の行なので 1 です。入力例 3 はすべての行が前に来るので、lo が n の 2 まで進みます。mid を (lo + hi) / 2 ではなく lo + (hi - lo) / 2 で求めているのは、lo + hi が size_t の範囲を超えないようにするためです。データベースの複合インデックスも同じ順序で並んでいるので、1列目を等号で決め、2列目を範囲で絞る検索は、この下限から始まる連続した範囲を読むだけで済みます。