Select Page

Binary Search Algorithm with Example | Data structures

Written by Quadrum Lee

February 17, 2020

Binary search will take less time than the linear search.
The one pre-request of binary search- Array should be sorted.
If the data is not sorted in the array, you cannot apply a binary search. Simply, you have to first sort the array and then apply the binary search. This is not the case in linear search and it works well in both sorted and unsorted array. Now, let see how the binary search algorithm works with the following example.

1) Introduction

What we search? – In here, we are going to search for the data 59 from the array and if 59 exist in the array, it should return the index of 59.
The more important point about this binary search algorithm is that it uses divide and conquer technique. It means it is going to divide the array into two half recursively. In this case, we’re going to find out the middle element of the array. So we get 2 variables L (left) and R (right).

2) Steps to search using binary search algorithm

Step 1 – 

L = 0 and R = 9

Now we need to find the mid-position of the array where we divide the array into 2 half. We can find it using the equation (L+R) / 2 and takes the flow value of it. So (0+9) / 2 is 4.5 and the flow value is 4.

In here, there are 3 cases can be occurred and let’s take a is the array,

1. The data you find out is equal to the data in the mid position.
Case 1 :- data == a[mid]

2. The data is less than the data which is in the mid position.
Case 2:- data < a[mid]

3. The data is greater than the data which is in the mid position.
Case 3 :- data > a[mid]


Step 2 –

The data we searched for 59 is passed the condition in case 3. It means 59 is greater than the mid element of the array. So we can say that the data is present on the right subarray. It is because this is a sorted array and all the elements greater than mid(25) must be present to the right of the mid element. Now L becomes Mid+1

L=5 and R=9

Now take the mid-index using (L+R) /2 and it is 7.


Step 3 – 

In this time, our searched value 59 is less than the mid-value which is passed the case 2. So data is present to the left of mid (63). Now R becomes Mid – 1 which is 6.

Take the mid index again. (5 + 6) / 2 and the result is  5. Now both L and Mid are 5.


Step 4 – 

Now again need to check the cases. 59 is greater than mid-value (45) and fulfil the case 3. If fulfil case 3, L becomes Mid + 1 and the index of it will be 6. 

Take the mid index again. (6 + 6) / 2 and the result is  6. Mid is also 5.

Now check the cases and searched data is equal to the Mid value. So it fulfils the case 1 and it is where we should stop the recursion. Now we found the data and we need to return the Mid.

03) What if searched data is not found in the array?

Even there is no searched value in the array, it will take up to step 4.

Now search value 59 is greater than Mid value (58).  So L becomes 6+1 and the result is 7. Now, this is the stopping place.  If L value becomes greater than R value, it means data is not present here.

04) Implementation of binary search

int binarySearch(arr, n, data) {
  int L = 0;
  int R = n;

  int mid = (L + R) / 2;

 while(L < R) {
   if (a[mid] == data) {
     return mid;
   } else if (data > a[mid]) {
    L = mid + 1;
   } else if (data < a[mid]) {
    R = mid - 1;
   } else {
    return -1;
   }
 }
}

0 Comments

Submit a Comment

Your email address will not be published. Required fields are marked *

Related Articles

Cool Gadgets on Amazon 2019 | Cool Amazon Products

Cool Gadgets on Amazon 2019 | Cool Amazon ProductsG, 0 Comments Today’s, topic about Cool Gadgets on Amazon 2019. Now, let's go and know about those gadgets in more deep. 01. The orange screwThis is one of the most clever and versatile tools you'll ever...

Is Interstellar Travel Impossible? | Interstellar Travel

Is Interstellar Travel Impossible? | Interstellar TravelG, 0 Comments Today's, topic about Interstellar Travel Impossible. Let's go into deep and understand the scientific facts related to this topic. Simply, Is interstellar travel doomed to remain in the...

Smart Retail Technology in IoT – Smart Retail Stores

Smart Retail Technology in IoT – Smart Retail StoresG, 0 Comments Today's topic is about "How IOT Gives Rise to Smart Retail Technology". Simply, I want you to picture your kitchen at home. If you're like most people you can trace many of your...

Stay Up to Date With The Latest News & Updates

Join Our Newsletter

Follow Us