All About Binary Search

By Gary Haidee On Mar 9, 2022

As defined by Wikipedia, an algorithm is a finite sequence of well-defined instructions, typically used to solve a class of specific problems or to perform a computation. They are used as specifications for performing calculations and data processing.

So, an algorithm is at the core of programming. When you start solving a problem, you usually don’t start with code; but you start with writing an algorithm. Computers know what to do just because of these algorithms.

Algorithms enable you to build more efficient code and solve various problems in programming. Most importantly, algorithms are easy to understand and don’t rely on any specific language and thus they are easily readable.

There are numerous algorithms that are applicable to different situations. One such efficient algorithm is the binary search which is used when you wish to find an item from a sorted list of items.

How Binary Search Works?

Binary search is typically used when you have a sorted list of items and you wish to search a particular item. It works by dividing the list of given items into half repeatedly until you have achieved the desired value.

You can use Binary Search in daily life problems. For instance, you are provided a sorted list and asked to find a specific element. Probably, you would go through the list iteratively in order to find out whether the item is there in the list or not. This solution is feasible when the number of items in the list is a handful only. What if the list contains thousands of items or even more?

It is here that binary search works. It efficiently and quickly finds out an element if it is provided with a sorted list of elements.

Let’s have a look at an example showing how binary search works.

Suppose that you have a list of 11 elements and you want to look for the number 8.

0 1 2 3 4 5 6 7 8 9 10

The point to be noted here is that binary search works on the principle of divide and conquer. This method works by dividing the given list into smaller lists of the same size until we get the desired result.

When we break down a given problem into smaller chunks means splitting the list into smaller ones. So, let’s identify what is in the middle of the given list.

↓ MID

0 1 2 3 4 5 6 7 8 9 10

After identifying the middle element, you are now required to compare the mid-value to the desired value. Here, the desired value is 7.

The three possibilities here are:

If the value is exactly the same as the desired value, we have got the result
If the mid-value is greater than the desired value, discard the first part of the list and take the second one and iterate the same procedure
If the mid-value is lesser than the desired value, discard the second part and iterate the procedure with the first one

We know that the desired value is 7, which is greater than 6; so we will proceed with the second half of the list.

Now, we have a new list where the items are as follows:

↓ MID

0 1 2 3 4

Now, when we follow the same step and divide the list into two halves, the new mid-value obtained here is 9.

Now, 9 is greater than 7 (desired value), so we will discard the second half of the list and proceed with the first half.

Now, the first half of the list is as shown below:

0 1

Now we have just two numbers in the list. We will compare both the numbers with the desired numbers. Clearly, we have got 7 as the first part of the list and hence we have got the desired number. So the second part of the list is discarded. Now, Stop.

One thing to be noted here is that binary search works only when you have a sorted list of elements. This is why this algorithm considers the mid-value of the list as the average value of the list. If your list is not sorted, you cannot use a binary search algorithm.

Importance of Binary Search Algorithm

Binary Search is commonly referred to as O(log n) which implies that the time complexity of your operation is proportional to the logarithm of its size.

In the above example, we had a list of 11 elements, we applied the operation three times to identify the desired element, revealing the efficiency of this algorithm. Traditional iteration of the list will require you to go through the list seven times in order to return the value 7. So, a binary search algorithm is faster than the traditional (linear search) iteration method.

Just imagine that you are given a list of thousand numbers and you have to find a specified element. Can you think of performing a linear search? Binary search is an ideal solution when you have a sorted list of thousands of elements and you have to find the particular element.

Conclusion

Algorithms are important when you are required to perform specific operations. They help you understand the logic behind your problem and improve your problem-solving skills. Binary search is an important algorithm to search an element in an arranged list of numerous elements.

To learn the practical implications of this algorithm, the simplest and most feasible way is to take up an online training course. With an online training course from Simplilearn, you can have an introduction to all the sorting algorithms including binary search, bubble sort, Quicksort, and more.

The skills you will acquire by taking up this course are:

To work with different kinds of sorting algorithms
Basics of sorting data structures
Selecting the relevant algorithm for different scenarios

You can take up this course if you are an aspiring software developer, data scientist, data analyst, AI engineer, coder, or simply a programming enthusiast.

Enrol Now!!