Suppose we have a discrete ordered list of times, and a number of events are evenly distributed throughout, and occur with equal probability at each time (but the overall process is deterministic and event times are fixed). We wish to locate the first such event, but queries are expensive and give only limited information.
I have two variations on the question:
We can only query: has at least one event occurred before time t?
We can only query: has at least one event occured before time t, and if so, what is a unique identifier (i.e. we can distinguish whether the last event has changed between two queries, but nothing else)?
For each of these scenarios (or at least one if you can answer), what is the algorithm that minimizes the number of queries? If we knew exactly one event occured, then binary search should be the fastest, but I'm not certain what the best is for unknown numbers of events.