Grokking Algorithms

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.

---

3
Binary search
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 
K
s. But you’re 
more likely to start at a page in the middle, because you know the 
K
s 
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 
A
s 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
.