In this chapter
• You get a foundation for the rest of the book.
• You write your first search algorithm (binary search).
• You learn how to talk about the running time of an algorithm (Big O notation).
• You’re introduced to a common technique for designing algorithms (recursion).
Introduction
An algorithm is a set of instructions for accomplishing a task. Every piece of code could be called an algorithm, but this book covers the more interesting bits. I chose the algorithms in this book for inclusion because they’re fast, or they solve interesting problems, or both. Here are some highlights:
• Chapter 1 talks about binary search and shows how an algorithm can speed up your code. In one example, the number of steps needed goes from 4 billion down to 32!
• A GPS device uses graph algorithms (as you’ll learn in chapters 6, 7, and 8) to calculate the shortest route to your destination.
• You can use dynamic programming (discussed in chapter 9) to write an AI algorithm that plays checkers.
In each case, I’ll describe the algorithm and give you an example. Then I’ll talk about the running time of the algorithm in Big O notation. Finally, I’ll explore what other types of problems could be solved by the same algorithm.
What you’ll learn about performance
The good news is, an implementation of every algorithm in this book is probably available in your favorite language, so you don’t have to write each algorithm yourself! But those implementations are useless if you don’t understand the trade-offs. In this book, you’ll learn to compare trade-offs between different algorithms: Should you use merge sort or quicksort? Should you use an array or a list? Just using a different data structure can make a big difference.
What you’ll learn about solving problems
You’ll learn techniques for solving problems that might have been out of your grasp until now. For example:
• If you like making video games, you can write an AI system that follows the user around using graph algorithms.
• You’ll learn to make a recommendations system using k-nearest neighbors.
• Some problems aren’t solvable in a timely manner! The part of this book that talks about NP-complete problems shows you how to identify those problems and come up with an algorithm that gives you an approximate answer.
More generally, by the end of this book, you’ll know some of the most widely applicable algorithms. You can then use your new knowledge to learn about more specific algorithms for AI, databases, and so on. Or you can take on bigger challenges at work.
What you need to know
You’ll need to know basic algebra before starting this book. In particular, take this function: f(x) = x × 2. What is f(5)? If you answered 10, you’re set.
Additionally, this chapter (and this book) will be easier to follow if you’re familiar with one programming language. All the examples in this book are in Python. If you don’t know any programming languages and want to learn one, choose Python—it’s great for beginners. If you know another language, like Ruby, you’ll be fine.
Binary search
Suppose you’re searching for a person in the phone book (what an old-fashioned sentence!). Their name starts with K. You could start at the beginning and keep flipping pages until you get to the Ks. But you’re more likely to start at a page in the middle, because you know the Ks are going to be near the middle of the phone book.
Or suppose you’re searching for a word in a dictionary, and it starts with O. Again, you’ll start near the middle.
Now suppose you log on to Facebook. When you do, Facebook has to verify that you have an account on the site. So, it needs to search for your username in its database. Suppose your username is karlmageddon. Facebook could start from the As and search for your name—but it makes more sense for it to begin somewhere in the middle.
This is a search problem. And all these cases use the same algorithm to solve the problem: binary search.
Binary search is an algorithm; its input is a sorted list of elements (I’ll explain later why it needs to be sorted). If an element you’re looking for is in that list, binary search returns the position where it’s located. Otherwise, binary search returns null.
Here’s an example of how binary search works. I’m thinking of a number between 1 and 100.
You have to try to guess my number in the fewest tries possible. With every guess, I’ll tell you if your guess is too low, too high, or correct.
Suppose you start guessing like this: 1, 2, 3, 4 …. Here’s how it would go.
This is simple search (maybe stupid search would be a better term). With each guess, you’re eliminating only one number. If my number was 99, it could take you 99 guesses to get there!
A better way to search
Here’s a better technique. Start with 50.
Too low, but you just eliminated half the numbers! Now you know that 1–50 are all too low. Next guess: 75.
Too high, but again you cut down half the remaining numbers! With binary search, you guess the middle number and eliminate half the remaining numbers every time. Next is 63 (halfway between 50 and 75).
This is binary search. You just learned your first algorithm! Here’s how many numbers you can eliminate every time.
Whatever number I’m thinking of, you can guess in a maximum of seven guesses—because you eliminate so many numbers with every guess!
Suppose you’re looking for a word in the dictionary. The dictionary has 240,000 words. In the worst case, how many steps do you think each search will take?
Simple search could take 240,000 steps if the word you’re looking for is the very last one in the book. With each step of binary search, you cut the number of words in half until you’re left with only one word.
So binary search will take 18 steps—a big difference! In general, for any list of n, binary search will take (log_2 n)*[linear] steps to run in the worst case, whereas simple search will take n steps.
Logarithms
You may not remember what logarithms are, but you probably know what exponentials are. log 10 100 is like asking, “How many 10s do we multiply together to get 100?” The answer is 2: 10 × 10. So log 10 100 = 2. Logs are the flip of exponentials.
In this book, when I talk about running time in Big O notation (explained a little later), log always means log 2 . When you search for an element using simple search, in the worst case you might have to look at every single element. So for a list of 8 numbers, you’d have to check 8 numbers at most. For binary search, you have to check log n elements in the worst case. For a list of 8 elements, log 8 == 3, because 2 3 == 8. So for a list of 8 numbers, you would have to check 3 numbers at most. For a list of 1,024 elements, log 1,024 = 10, because 2 10 == 1,024. So for a list of 1,024 numbers, you’d have to check 10 numbers at most.
Note
I’ll talk about log time a lot in this book, so you should understand the concept of logarithms. If you don’t, Khan Academy (khanacademy.org) has a nice video that makes it clear.
Note
Binary search only works when your list is in sorted order. For example, the names in a phone book are sorted in alphabetical order, so you can use binary search to look for a name. What would happen if the names weren’t sorted?
GrayCS 