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列目を範囲で絞る検索は、この下限から始まる連続した範囲を読むだけで済みます。