G3 · Pupil · 7 min
Monotonic Oracle
Lamps are off, then on, with a single cut. Ask an index; the oracle reveals that lamp. Find the first on lamp before the query budget hits zero.
query budget
6
Lamps are off, then on. Find the first on (or 16 if all are off). Binary search spends this budget; linear scan does not.
Commit first-true index: