Chapter 1 of Grokking Algorithms

In Chapter 1—You’ll learn the first practical algorithm: binary search and learn to analyze the speed of an algorithm using Big O notation. Big O notation is used throughout the book to analyze how slow or fast an algorithm is.

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!

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.

An algorithm is a set of instructions for accomplishing a task. Every piece of code could be called an algorithm.

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.

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, the binary search returns null.

A bad approach to number-guessing

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 a simple search (maybe a 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 a binary search. 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?

A 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 log2 n steps to run in the worst case, whereas simple search will take n steps.

Eliminate half the numbers every time with a binary search.

Binary search Logarithms

You may not remember what logarithms are, but you probably know what exponentials are. log10 100 is like asking, “How many 10s do we multiply together to get 100?” The answer is 2: 10 × 10. So log10 100 = 2.

Logs are the flip of exponentials.

I talk about running time in Big O notation, log always means log2.

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: you should understand the concept of logarithms. If you don’t, Khan Academy (khanacademy.org) has a nice video that makes it clear.

The binary_search function takes a sorted array and an item. If the item is in the array, the function returns its position. You’ll keep track of what part of the array you have to search through.

Implement a Binary Search Algorithm

low = 0

high = len(list) - 1

Each time, you check the middle element: mid = (low + high) / 2, guess = list[mid]

mid is rounded down by Python automatically if (low + high) isn’t an even number.

If the guess is too low, you update low accordingly:

if guess < item: low = mid + 1

If the guess is too high, you update low accordingly:

if guess > item: high = mid - 1

Using left + (right - left) / 2 in binary search instead of (right + left) / 2 helps to prevent potential overflow issues in languages with fixed integer sizes.

Explanation:

1. Overflow Risk:

• In some programming languages, if left and right are large integers, adding them directly can exceed the maximum integer value, causing an overflow. For example, if left = 2^31 - 1 and right = 2^31 - 1, their sum would be 2^32 - 2, which is not representable in a 32-bit signed integer.

2. Safe Calculation:

• Using left + (right - left) / 2 ensures the calculation stays within the bounds of the integers, reducing the risk of overflow: right - left is guaranteed to be non-negative (or zero). Dividing by 2 keeps the value smaller, and adding left at the end avoids exceeding limits.

Running time

Generally, you want to choose the most efficient algorithm— whether you’re trying to optimize for time or space.

Back to binary search. How much time do you save by using it? Well, the first approach was to check each number, one by one. If this is a list of 100 numbers, it takes up to 100 guesses. If it’s a list of 4 billion numbers, it takes up to 4 billion guesses. So the maximum number of guesses is the same as the size of the list. This is called linear time.

Binary search is different. If the list is 100 items long, it takes at most 7 guesses. If the list is 4 billion items, it takes at most 32 guesses. Powerful? The binary search runs in logarithmic time.

Big O notation

Big O notation is a special notation that tells you how fast an algorithm is. Who cares? Well, it turns out that you’ll use other people’s algorithms often—and when you do, it’s nice to understand how fast or slow they are. In this section, I’ll explain what Big O notation is and give you a list of the most common running times for algorithms using it.

Binary search is about 15 times faster than simple search, because simple search took 100 ms with 100 elements, and binary search took 7 ms. So simple search will take 30 × 15 = 450 ms

Big O notation tells you how fast an algorithm is. For example, suppose you have a list of size n. A simple search needs to check each element, so it will take n operations. The run time in Big O notation is O(n). Where are the seconds? There are none—Big O doesn’t tell you the speed in seconds. Big O notation lets you compare the number of operations. It tells you how fast the algorithm grows.

Here’s another example. Binary search needs log n operations to check a list of size n. What’s the running time in Big O notation? It’s O(log n).

This tells you the number of operations an algorithm will make. It’s called Big O notation because you put a “big O” in front of the number of operations.

Visualizing different Big O run times

Here’s a practical example you can follow at home with a few pieces of paper and a pencil. Suppose you have to draw a grid of 16 boxes.

Algorithm 1

One way to do it is to draw 16 boxes, one at a time. Remember, Big O notation counts the number of operations. In this example, drawing one box is one operation. You have to draw 16 boxes. How many operations will it take, drawing one box at a time?

It takes 16 steps to draw 16 boxes. What’s the running time for this algorithm?

Algorithm 2

Try this algorithm instead. Fold the paper. In this example, folding the paper once is an operation. You just made two boxes with that operation!

Fold the paper again, and again, and again. Unfold it after four-folds, and you’ll have a beautiful grid! Every fold doubles the number of boxes. You made 16 boxes with 4 operations!

You can “draw” twice as many boxes with every fold, so you can draw 16 boxes in 4 steps.

What’s the running time for this algorithm? Come up with running times for both algorithms before moving on. Answers: Algorithm 1 takes O(n) time, and algorithm 2 takes O(log n) time.

Big O establishes a worst-case run time

Suppose you’re using a simple search to look for a person in the phone book. You know that simple search takes O(n) time to run, which means in the worst case, you’ll have to look through every single entry in your phone book.

In this case, you’re looking for Adit. This guy is the first entry in your phone book. So you didn’t have to look at every entry—you found it on the first try. Did this algorithm take O(n) time? Or did it take O(1) time because you found the person on the first try? Simple search still takes O(n) time.

In this case, you found what you were looking for instantly. That’s the best-case scenario. But Big O notation is about the worst-case scenario. So you can say that, in the worst case, you’ll have to look at every entry in the phone book once. That’s O(n) time. It’s a reassurance—you know that a simple search will never be slower than O(n) time.

Along with the worst-case run time, it’s also important to look at the average-case run time.

Some common Big O run times

Here are five Big O run times that you’ll encounter a lot, sorted from fastest to slowest:

• O(1), Example: If Condition.
• O(log n), also known as log time. Example: Binary search.
• O(n), also known as linear time. Example: Simple search.
• O(n * log n). Example: A fast sorting algorithm, like quicksort.
• O(n2). Example: A slow sorting algorithm, like selection sort.
• O(n!). Example: A slow algorithm, like the traveling salesperson.

The main takeaways are as follows:

• Algorithm speed isn’t measured in seconds but in the growth of the number of operations.
• Instead, we talk about how quickly the run time of an algorithm increases as the size of the input increases.
• The run time of algorithms is expressed in Big O notation.
• O(log n) is faster than O(n), but it gets a lot faster as the list of items you’re searching grows.

The traveling salesperson

“There’s no way I’ll ever run into an algorithm that takes O(n!) time.” Well, let me try to prove you wrong! Here’s an example of an algorithm with a really bad running time. This is a famous problem in computer science because its growth is appalling and some very smart people think it can’t be improved. It’s called the traveling salesperson problem.

You have a salesperson, The salesperson has to go to five cities, This salesperson, whom I’ll call Opus, wants to hit all five cities while traveling the minimum distance.

He adds up the total distance and then picks the path with the lowest distance. There are 120 permutations with 5 cities, so it will take 120 operations to solve the problem for 5 cities. For 6 cities, it will take 720 operations (there are 720 permutations). For 7 cities, it will take 5,040 operations.

In general, for n items, it will take n! (n factorial) operations to compute the result. So this is O(n!) time, or factorial time. It takes a lot of operations for everything except the smallest numbers.

Once you’re dealing with 100+ cities, it’s impossible to calculate the answer in time—the Sun will collapse first. This is a terrible algorithm! Opus should use a different one, right? But he can’t. This is one of the unsolved problems in computer science. There’s no fast known algorithm for it, and smart people think it’s impossible to have a smart algorithm for this problem.

The best we can do is come up with an approximate solution; see Chapter 10 for more. One final note: if you’re an advanced reader, check out binary search trees! There’s a brief description of them in the last chapter.

Recap

• Binary search is a lot faster than simple search.
• O(log n) is faster than O(n), but it gets a lot faster once the list of items you’re searching through grows. • Algorithm speed isn’t measured in seconds.
• Algorithm times are measured in terms of the growth of an algorithm.
• Algorithm times are written in Big O notation