Algorithms: Simple Search
Imagine you are visiting your friend Guido’s house and he asks you to find his favorite book from the Harry Potter series, “The Prisoner of Azkaban.” How would you do it?
The simplest method and often the first that comes to mind is to look through each book, one by one, until you find the correct title. Let’s call this approach Simple Search. We can implement it in Python as follows:
books = ['The Philosopher’s Stone', 'The Chamber of Secrets', 'The Prisoner of Azkaban', 'The Goblet of Fire', 'The Order of the Phoenix', 'The Half-Blood Prince', 'The Deathly Hallows'] for book in books: if book == 'The Order of the Phoenix': print("I found...", book) // I found... The Order of the Phoenix
We’ve created a list called
books that has all the titles. Then we used a simple
for loop to loop over every item in the list, check if an item equals “The Order of the Phoenix,” and then print out the title of the book.
book here could be named anything. We could also have named it
anything_at_all and it would have worked. The important thing is that the name of our list,
books, matches the
books in our
for anything_at_all in books: if anything_at_all == 'The Order of the Phoenix': print("I found...", book)
Ok, so we found the book! How many books did we have to search through before we arrived at our destination? In this example, we wanted the 5th book and since the books were in order, 1-7, we had to look through 5 of the 7 books to find it.
But since programmers are lazy, we want to have the computer count the number of steps for us next time. If we add a simple counter variable,
i, we can see this in action:
i = 0 for book in books: i += 1 if book == 'The Order of the Phoenix': print(i, book) break // 5 The Order of the Phoenix
In the best case scenario, Guido asks us to find the first book, “The Philosopher’s Stone,” which takes 1 step, but in the worst case he asks for the last book, “The Deathly Hallows,” which takes all 7 steps. Therefore in our Simple Search algorithm, the number of steps required in the worst case equals the number of inputs.
No big deal here, but what if we were searching through 100 books or even 1 million? Is there a more efficient algorithm to find a given book in a sorted list?
Indeed there is. It’s called Binary Search.