Leonardo Maldonado Full Stack Developer. JavaScript, React, TypeScript, GraphQL.

Why binary search is useful

4 min read 1182

Why binary search is useful

Computer programming would not be the same without algorithms. Without algorithms, computer programming may not even exist. Computers only know what to do because of algorithms.

Algorithms help us to build more efficient code and solve specific problems in programming. They can help us in a lot of different situations.

Algorithms are very easy to understand, they’re not dependent on any specific language, even people who are not developers can learn algorithms easily.

The importance of algorithms

As MathVault defined, algorithms are:

A finite series of well-defined, computer-implementable instructions to solve a specific set of computable problems. It takes a finite amount of initial input(s), processes them unambiguously at each operation, before returning its outputs within a finite amount of time.

We are using algorithms in everything. Software, applications, frameworks, libraries, etc. all have some algorithms running under the hood helping solve problems and improve performance. They are also talked about in developer interviews, to know how a developer thinks and handles logic.

Imagine a person that likes to play guitar, this person knows very well how to play a few songs but they don’t know a lot of music theory. Learning about music theory before playing an instrumental is not mandatory, but it will certainly help you to understand a few important concepts that need to be known. It will show another universe of music to this person, how music exactly works, how to play the right notes, etc.

The same applies to algorithms and developers. You can be a software developer and not know about algorithms. A lot of people nowadays start to learn how to program and don’t start with algorithms but being familiar with algorithms can help you think about code and solving problems.

How binary search works

We might encounter a lot of situations on a daily basis that we can use binary search to solve it. For example, when we want to search a specific element inside a list of elements, the most common solution that we find is to iterate all over the list and return the element if it exists.

But this might be a problem, especially if we want to search a specific element inside a huge list, it will result in bad performance and take too long to run. Imagine that we have a list of one million elements and we want to search a specific element of that list, in the worst case we would make one million operations.

Binary search is a very efficient and fast algorithm to find an element inside a sorted list of elements, this algorithm works based on the principle of divide and conquer.

We made a custom demo for .
No really. Click here to check it out.

The first step for a binary search algorithm to work is to have the list of elements sorted. Imagine that we have a list of 12 elements, and we want to look for the number 8, for example.

numbers 1-11 in binary search

Remember that binary search works with the principle of divide and conquer. The divide and conquer method works by breaking down a problem into a few smaller problems of the same size until they are a few simple problems.

Breaking down our problem into one or more sub-problems, in our case, means to split one problem into a few smaller problems. But first, we need to determine the middle of our list of elements and divide our list by two.

middle of numbers in line

After we find the mid element of the list, we need to make a comparison. We need to compare the value of the element that we want with the value of the mid element of the list.

There are now three possible ways:

  1. The value that we are looking for is exactly the same as the middle element of our list, so we return it
  2. The value that we are looking for is lesser than the value of the mid element, so we will discard the second part of the list and continue with the first one
  3. The value that we are looking for is greater than the value of the mid element, so we will discard the first part of the list and continue with the first one

In our case, the value that we are looking for is greater than the value of the mid element, so we will discard the first part of the list and continue with the second one.

7, 8, 9, 10, 11 all in a row

Now we have a new list of elements, we need to do the same process again, find the mid element of our list, and compare it to the value that we want.

numbers 7,8,9,10,11 with number 9 highlighted in red

The value that we are looking for is lesser than the value of the middle element, so we can discard the second part of the list and continue with the first part.

7,8 in a row

We are going to do the same process here, divide the list into two parts, find the middle element, and compare the value to the number that we are looking for.

Since we only have two elements in the list, the mid element will be the first one. The element that we want has a greater value than the value of the mid element, so we got to the end of our operation with the desired element returned.

One thing that should be taken into consideration here is that binary search only works in a sorted list of elements, that’s why binary search already assumes that the mid element of the list contains the median value of the list. In case the list of elements is not sorted, there’s no way to use binary search because the median value of the list can be anywhere and when the list is split into two parts, the element that you were searching for could be cut off.

Why is it useful?

Binary search is known for being an O(log n) which means that the time complexity of our operation is proportional to the logarithm of its input size.

In this example, with a list of 12 elements, we only made 3 operations to return the desired element, that’s very impressive and very efficient. Iterating all over the list just to return a specific element, in this example, we would make at least 8 operations. This performance would not be fast and efficient and we would end up with a function of linear time complexity.

Now just imagine that we wanted to search an element inside a list of one million elements, we would still be able to run the operation pretty fast and efficient. We always need to consider the worst-case in these scenarios, and to search for a specific element inside a sorted list of elements, binary search is ideal for that.

Conclusion

Algorithms have an important part in our lives, they are responsible for passing the instructions and telling the computers what to do. Algorithms can help us understand and improve logical thinking, consider different approaches for a specific situation, and choose the right solution for a problem. Binary search is a very efficient and fast algorithm to search an element inside a sorted list of elements, and it can be very useful.

: Full visibility into your web apps

LogRocket is a frontend application monitoring solution that lets you replay problems as if they happened in your own browser. Instead of guessing why errors happen, or asking users for screenshots and log dumps, LogRocket lets you replay the session to quickly understand what went wrong. It works perfectly with any app, regardless of framework, and has plugins to log additional context from Redux, Vuex, and @ngrx/store.

In addition to logging Redux actions and state, LogRocket records console logs, JavaScript errors, stacktraces, network requests/responses with headers + bodies, browser metadata, and custom logs. It also instruments the DOM to record the HTML and CSS on the page, recreating pixel-perfect videos of even the most complex single-page apps.

.
Leonardo Maldonado Full Stack Developer. JavaScript, React, TypeScript, GraphQL.

Leave a Reply