Lily's Bookshelf

Computer Science Level 2

Lily has a bookshelf on which 63 books are neatly arranged in alphabetical order, and she is now looking for her favorite combinatorics book.

Using the best approach, what is the maximum number of books she would have to check?

The answer is 6.

1 solution

Ossama Ismail
Mar 2, 2017

Lily may use binary search algorithm to find here favorite book. Binary search (half-interval search) is one of the fundamental algorithms in computer science. Binary search runs in at worst logarithmic time, making $\log_2(n)$ time. In this case, the maximum number of books to be checked is $\log_2(63) = 5.997 \implies 6$ books.

Playing devil's advocate, how do we know that there isn't a faster approach?

Calvin Lin Staff - 4 years, 3 months ago

That's interesting. I have never thought about this before.

Agnishom Chattopadhyay - 4 years, 3 months ago

Any algorithm that works by comparison must be equivalent to a decision tree whose inner nodes are the comparisons, and the leaves are the positions of the books. Because the depth of a binary tree on $n$ nodes is at least $\Omega(\lg n)$ , we cannot hope to have an algorithm that works better.

Agnishom Chattopadhyay - 3 years, 10 months ago

She doesn't have to check the last book, though - she'll already know what it is.

Gregory Lewis - 3 years, 10 months ago

She must check the last book. You have to consider the case when the book is not on the shelf.

Ossama Ismail - 3 years, 10 months ago

Info: Binary search is the best deterministic way to find an element in a sorted list. Because you can just compare 2 books at the same time, you can just half the search range.

Izan BF - 3 years, 10 months ago

Lily's Bookshelf

The answer is 6.

1 solution

0 pending reports