How would I find a book in a large library?

Question

I found the following question while preparing for an interview:

You are in a very huge library that has no computer access, and you're looking for one particular book.

You look up where the book suppose to be from the card catalog, and went to shelf X to find it.

However the book is not there.

There is only one person that can answer questions, which is the libarian, but he only answers yes/no responses. Plus, his answers might not be correct.

What is your strategy for finding this book?

How would you answer this question? What methods of searching would you use?

Answer 1

Use Binary search type questions to narrow the location of the book.

Each question should narrow the search field by half.

"Is the book on this half of the library"? (Point to the right direction).

Would work as an initial question.

You can also use The Knight and the Knave as part of your method of questioning the person. Your first 5 questions (to establish a baseline) could be about things you 'know'. You could determine his error rate from there. After that, you can use Binary Search-esque questions to determine where the book is.

Answer 2

1. Ask the interviewer for more information about the librarian and go from there. In particular, find out if he's susceptible to bribery (I mean the librarian, but come to think of it this might go for the interviewer as well).
2. Double-check for dumb mistakes (wrong card, wrong shelf, "661-88" is reall "88-199" and so on).
3. Search the drawer of borrowed-book cards. If it's been borrowed, note the due date and come back later, or note the borrower's home address and go to plan B.
4. Look in the vicinity, a few books in either direction and the shelves above and below, in case it was incorrectly reshelved.
5. Check the tables, floors, photocopiers and return carts.
6. Look for a gap on the shelf. If there is a gap in the right spot then at least you know you're looking in the right place. If there's no gap then look for a book on that shelf that doesn't belong-- somebody may have swapped them by mistake. If there's no such misplaced book then maybe the book was never on this shelf, see below.
7. Look for dust on the shelf. It might indicate whether a book has been removed within the past month. Likewise check the index card for signs of age. The flowchart gets a little complicated, but the book may have been lost years ago.
8. Check the index system: if the book doesn't have the right number for its subject/title/author/whatever, then there is a typo on the index card and you must calculate the correct number yourself to find out where the book really is.
9. Just go out and buy the damned book, your time is more valuable than this.