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.
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.
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.
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.
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.
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:
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.
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.
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.
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.
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.
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.
Install LogRocket via npm or script tag. LogRocket.init() must be called client-side, not
server-side
Learn more →
$ npm i --save logrocket
// Code:
import LogRocket from 'logrocket';
LogRocket.init('app/id');
// Add to your HTML:
<script src="https://cdn.lr-ingest.com/LogRocket.min.js"></script>
<script>window.LogRocket && window.LogRocket.init('app/id');</script>
Hey there, want to help make our blog better?
Join LogRocket’s Content Advisory Board. You’ll help inform the type of content we create and get access to exclusive meetups, social accreditation, and swag.
Sign up now
Use CSS to style and manage disclosure widgets, which are the HTML `details` and `summary` elements.
React Native’s New Architecture offers significant performance advantages. In this article, you’ll explore synchronous and asynchronous rendering in React Native through practical use cases.
Build scalable admin dashboards with Filament and Laravel using Form Builder, Notifications, and Actions for clean, interactive panels.
Break down the parts of a URL and explore APIs for working with them in JavaScript, parsing them, building query strings, checking their validity, etc.
One Reply to "Why binary search is useful"
Nice & clean explanation, thanks!