The following puzzle deals with storage and search strategies for querying membership of elements in a table. Like the light bulb puzzle, it’s an example of a situation where binary search is only optimal in the limiting case. I will try to present the problem in the same weirdly racy context in which I first encountered it:
You are the manager of a hotel that, once a year, hosts members of a secretive private club in numbered suites on a dedicated floor of the hotel. There are club members, known to you only by numbers 1 through . Each year, some subset of 10 of the 18 club members come to the hotel for a weekend, each staying in his own suite. To preserve secrecy, you assign each man to a suite… but then destroy your records, including the list of the particular members staying that weekend.
It may be necessary to determine whether a particular member is staying at the hotel (say, upon receiving a call from his wife asking if her husband is there). But the club has asked that in such cases you must only knock on the door of a single suite to find out who is residing there. For a given subset of 10 club members, how should you assign them to suites, and what is your “single-query” search strategy for determining whether any given club member is staying at your hotel?
This problem is interesting because, for a sufficiently large universe of possible key values, we can minimize the maximum number of queries needed in a table of size by storing the keys in sorted order, and using binary search, requiring queries in the worst case. But for small , as in this problem, we can do better. For example, if , then we don’t need any queries, since every key is always in the table. If , then we can store in a designated position the key immediately preceding (cyclically if necessary) the missing one, requiring just a single query to determine membership.
(Hint: The problem is setup to realize a known tight bound: if , then there is a strategy requiring just a single query in the worst case.)