Being a line cook was a lot harder than Kenny thought! He wanted to find some more relaxing work so Kenny went and got a job at the small rare bookstore in town. Kenny finds that most of his time working at the bookstore is spent searching for rare books that customers request.
Sadly, the store isn’t separated into sections or labeled well, so Kenny finds himself going through row after row of books without any real direction. After a couple times of trying to look through every book from start to finish to find the one he needs, Kenny knows he needs to think of a better method, to optimize his search.
The good news is that the books are in alphabetical order, so Kenny thinks back to when he had to optimize searches when he was studying computer science and comes up with an idea. First, he’ll start on a middle shelf and check the name of the author there. If that author comes later in the alphabet than the one he’s looking for, he knows he only has to check the shelves on the left. If it comes before the author he’s looking for he only has to check the shelves on the right.
He can then repeat this method on whichever side of the store the book must be on and slowly narrow down the area where the book must be. After repeating this process a couple times he is able to pinpoint the book and find it for the customer. Kenny knows that what he ended up implementing was a binary search, in computer science terms, and it ended up being able to effectively optimize his search time and reduce the amount of shelf scanning he had to do by several fold.
Once again, his background in computer science is paying off!
Instructions
In the code editor, you’ll see two functions. linear_search() shows how Kenny was initially searching through the books in the store, while binary_search() shows the more efficient way Kenny developed to look for books.
Let’s try to find Do Androids Dream of Electric Sheep? by searching through the bookshelves using a linear search. Scroll to the bottom of the code editor and copy paste the code below to run the search:
How many books did we have to check before we found Do Androids Dream of Electric Sheep?? You might need to scroll the output up to see all of the books!
Next, let’s try to find Do Androids Dream of Electric Sheep? using a Kenny’s optimized method, a binary search.
Copy paste the code below into the bottom of the code editor to run the search.
How many books did we have to check before we found Do Androids Dream of Electric Sheep? this time?
Did Kenny’s new method of searching save time?