Linear vs Binary Search

Cathy Yee
Cathy Yee
Jul 24, 2017 · 4 min read

If you’ve written some code, you’ve probably written an algorithm. An algorithm is a step by step process of solving a problem. If I wanted to make chocolate milk, my algorithm will be

There are many different algorithms that can solve the same problem and finding the best algorithm to use can save time and memory.

Let’s take a look at this problem. Will be using JavaScript for this example.

Find the element in a sorted array that is equal to 12 and return the index. If there is no element equal to 12, return false.

In a sorted array, all the elements are in ascending order as opposed to a standard array where all the elements are in no particular order. Such as [19, 3, 12, 8, 15, 5].

The first time I saw this problem and being a beginner coder, I thought of taking a linear approach. In a linear approach, you go through all the elements starting from index 0 until you hit the element you’re looking for. Here’s how the answer would look like in JavaScript.

By going through all the elements starting at index 0, it took 3 steps to find the index. But if we wanted to find the index of number 31, it would take us 5 steps. And if the size of the array would double or triple, the number of steps to find the index will increase as well. Although this linear approach works, it’s not the best or most efficient way to solve a problem especially if you have 1000 elements in the array. It would take too much time and memory. Finding an algorithm to cut down on the number of steps to find the index would be better. This is where binary search will come in handy. Binary search can only be used in a sorted array not a standard array.

In a binary search you start in the middle of the array as oppose to the beginning. Let’s take the array in the earlier example and increase its size.

In this next problem, we want to find the index of number 41. There are 10 elements in this array. Instead of starting at index 0, we will start at index 5. At index 5, the number is 34. 34 is less than 41 so we can automatically eliminate 34 and all the numbers to the left of it. We can focus on the numbers to the right starting at 37.

From index 6 to index 9 we can go directly to index 8 which is approximately in the middle. At index 8 is number 41 — the number we are looking for.

Here’s how the solution would look like in JavaScript.

By using the binary search, it took us only 2 steps to find the index. If we had used the linear search, it would have taken us 9 steps. This is the power of a binary search and an example of how using the right algorithm for your solution can make a huge difference in how fast your code runs.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade