How to Use Binary Search To Find Things Faster🚀

Before we can even begin to understand Binary Search, let's first understand what searching is in general. We used to have a small alphabet book as kids that contained images and corresponding alphabets.

Our mom would ask us to find a random letter and we would open the book and search for the letter by referencing the image (For example M for Mango then you would search for a mango image in the book).

But as you grew up, you became an expert at finding the alphabet in the book. If your mom asked you to find M, then you would be smart enough to know that M will be on some centre page. You would start searching it directly from some random middle page 😎

Now let's just analyse the example that I gave.

If you think about it, there are two approaches you can take to find the alphabet.

1. Searching every page from the beginning until you find the alphabet.
2. Opening a random page and searching the alphabet.

The second method seems an intelligent move to find the alphabet the fastest way right😉

So now let me share something with you🤫

The first approach which we discussed is called Linear Search. You are linearly searching the alphabet without skipping a single page until you find the desired alphabet.

For finding the alphabet using Linear search we will start searching from page 1 until we get the alphabet we are looking for. Let's say you are searching for the letter D. Using Linear Search you will start from the letter A and keep flipping the page unless it's D.

This seems to be taking a long time, right? And did you think of searching for the letter Z? We would have to make 25 searches and after that, we would find Z😵‍💫

Imagine finding a word in the dictionary by using the Linear Search method😶‍🌫️

What is the fast alternative?🤔

Remember the second method, the smart move we made while searching the alphabet? Based on the alphabet we had to search we were opening pages randomly and searching them!

Let's discuss a little about this method.

So let's take an example of finding the letter M in the book. Suppose the page number is from 1 to 26 where on page 1 there is the letter A and so on. Now smartly you will think that the letter M lies somewhere in between i.e. on page 13. Tada, on page 13 there will be the letter M (Since M is the 13th alphabet). So for the linear search, you would take 13 steps to find M, but by using the smart way you found M in the first step!

Isn't that amazing?🤩

But remember this method will work only if the alphabets are in order. Otherwise, this method is useless and we will have to use the Linear search.

The smart way we have learned so far can help us locate any alphabet in a few steps. The only condition required is that the alphabet should be sorted. Binary Search is the smart way of doing this.

Let us now understand how binary search can help us find our desired output in a few steps. Let's take an example of finding the letter F.

Steps:

1. Find the middle element First, we will find the middle alphabet. Here the middle alphabet is the letter M.
2. Check if the target is greater or smaller than the middle element The letter F lies before the letter M. So we can say that the letter F is smaller than the middle alphabet.
3. If the target is smaller than the middle element then search on the left side So we will now check for the target from the start to the middle alphabet i.e. We will search for the letter F in between A and M.

So if you look closely we are reducing the range of searching and we are finding the target. The half of 13 is 6 (considering the integer value) and on page 6 there will be the letter F (Since F is the 6th alphabet). This is how we found the letter F in 2 steps using Binary Search.

To summarise, We need to follow the following steps for Binary search:

1. Find the middle element.
2. Check if the target is greater or smaller than the middle element.
3. If the target is greater than the middle element, search on the right-hand side.
4. Else, if the target is smaller than the middle element, search on the left-hand side.
5. Repeat steps 2, 3 and 4 till the middle element is equal to the target.

Let's take another example.

The first thing you should check before applying Binary Search is to check whether the given range is sorted. Once we verified, you can go ahead and apply binary search.

1. Find the middle element.

   The middle element in the above array is 11. (4th element in the array is 11)

   middle = (start + end) / 2 
   middle => (0 + 9) / 2 
   middle => 4
   

2. Check if the target is greater or smaller than the middle element.

   If the target element is greater than the middle element, check on the right side.

   if ( target > middle ) => check on the right
   

   Whereas, If the target element is smaller than the middle element, check on the left side.

   if ( target < middle ) => check on the left
   

   In our case, 36 > 11, thus we have to check on the right side.

Repeating steps 1 and 2 again.

middle = (start + end) / 2 
middle => (5 + 9) /2 
middle => 14 / 2 
middle => 7

The 7th element in the array is 20. In this case 36 > 20, thus we again have to check on the right side.

Repeating steps 1 and 2 again.

middle = (start + end) / 2 
middle => (7 + 9) /2 
middle => 16 / 2 
middle => 8

The 8th element in the array is 36. Hurray! we have finally found out 36.

If you see we have found 36 in just 4 steps. If we used linear search, we would require 8 steps to find 36.

Let's now understand the Time complexity of Binary search.

Here the space in which we are searching is getting divided into two parts.

In the first step, when the array is not split, the size of the array is,

N / 2^0

In the second step, it becomes

N / 2^1

In the third step, it becomes

N / 2^2

Thus at the k^th step,

N / 2^k = 1

It is equal to 1 because the size of the array is reduced to 1 element only i.e. the target element.

Thus if we solve this further,

N = 2^k    // Shifting 2^k on the Right side
log ( N ) = log ( 2^k )    // Taking log on both sides
log ( N ) = k * log( 2 )
log ( N ) / log ( 2 ) = k
k = log2 ( N )

Here k is the total number of comparisons done while finding the target element and N is the size of the array. Thus the time complexity of Binary search is O(log (N)).

Now that you have a fundamental understanding of Binary Search, you can easily understand its implementation in any programming language you like!

Did you find this useful?🤔 Feel free to like and save it to your timeline for reference later!😊

Thanks for reading ✨