At the local library, the librarian is responsible for helping patrons find books. To find books faster, the librarian stores the books on the shelves alphabetically by title. The library has a limited budget but wants to have the widest variety of books as possible, so they decided to only keep a single copy of any given title. A recent storm and electrical surge fried their electronic card catalog that tracks where books are stored on the shelves.

(a) When a patron comes in to look for a title, the librarian must help them locate the book, or report that it is checked out. While the library waits for a new electronic system, this must be done by personally looking through the inventory on the shelves. Give the decision tree the librarian should follow that avoids having to examine every book on the shelves, even in the situation that the book is checked out.

(b) Derive a tight lower bound for any retrieval algorithm to solve this problem using a decision tree.