Binary Search vs. Linear Search

With ordered arrays of a small size, the algorithm of binary search doesn’t have much of an advantage over linear search. But let’s see what happens with larger arrays.

With an array containing 100 values, here are the maximum number of steps each type of search would take:

• Linear search: 100 steps
• Binary search: 7 steps

With linear search, if the value we’re searching for is in the final cell or is greater than the value in the final cell, we have to inspect each and every element. For an array of size 100, this would take 100 steps.

When we use binary search, however, each guess we make eliminates half of the possible cells we’d have to search. In our very first guess, we get to eliminate a whopping fifty cells.

Let’s look at this another way, and we’ll see a pattern emerge.

With an array of size 3, binary search would take a maximum of two steps.

If we double the number of cells in the array (and add one more to keep the number odd for simplicity’s sake), there are seven cells. For such an array, the maximum number of steps to find something using binary search is three.

If we double it again (and add one) so that the ordered array contains fifteen elements, the maximum number of steps for binary search is four.

The pattern that emerges is that for each time we double the size of the ordered array, the number of steps needed for binary search increases by one. This makes sense, as each lookup eliminates half of the elements from the search.

This pattern is unusually efficient: each time we double the data, the binary search algorithm adds just one more step.

Contrast this with linear search. If you had 3 elements, you’d need up to 3 steps. For 7 elements, you’d need a maximum of 3 steps. For 100 values, you’d need up to 100 steps. With linear search, then, there are as many steps as there are items. So for linear search, each time we double the size of the array, we double the number of steps of our search. For binary search, though, each time we double the size of the array, we only need to add one more step.

Let’s see how this plays out for larger arrays. With an array of 10,000 elements, linear search can take up to 10,000 steps, while binary search takes up to a maximum of just 13 steps. For an array of size one million, linear search would take up to one million steps, while binary search would take up to just 20 steps.

We can visualize the difference in performance between linear and binary search with this graph:

We’ll be analyzing a bunch of graphs that look like this, so let’s take a moment to digest what’s going on. The x-axis represents the number of elements inside the array. That is, as we move from left to right, we’re dealing with an increasing amount of data.

The y-axis represents how many steps the algorithm takes. As we move up the graph, we’re looking at a greater number of steps.

If you look at the line representing linear search, you’ll see that as an array has more elements, linear search takes a proportionally increasing number of steps. Essentially, for each additional element in the array, linear search takes one additional step. This produces a straight diagonal line.

With binary search, on the other hand, you’ll see that as the data increases, the algorithm’s steps only increase marginally. This makes perfect sense with what we know: you have to double the amount of data just to add one additional step to binary search.

Keep in mind that ordered arrays aren’t faster in every respect. As you’ve seen, insertion in ordered arrays is slower than in standard arrays. But here’s the trade-off: by using an ordered array, you have somewhat slower insertion but much faster search. Again, you must always analyze your application to see which is a better fit. Will your software be doing many insertions? Will searching be a significant feature of the app you’re building?

Pop Quiz

I find the following pop quiz question really forces one to grasp the efficiency of binary search. Cover the answer and see if you get it right.

The question: We said that for an ordered array with 100 elements, binary search takes seven steps. How many steps would binary search take on an ordered array containing 200 elements?

The answer: Eight steps.

The intuitive answer I often hear is fourteen steps, but this is incorrect. The whole beauty of binary search is that each inspection eliminates half of the remaining elements. Therefore, each time we double the amount of data, we add only one step. After all, this doubling of data gets totally eliminated with the first inspection!

It’s worth noting that now that we’ve added binary search to our toolkit, insertion within an ordered array can become faster as well. Insertion requires a search before the actual insertion, but we can now upgrade that search from a linear search to a binary search. However, insertion within an ordered array still remains slower than within a regular array, as the regular array’s insertion doesn’t require a search at all.