Binary search is basically a searching algorithm used to search for a particular element in any given array. There are in fact many searching algorithms available, but what matters more is the efficiency with which an algorithm searches for an element in any given array because we would never want our algorithm to do less work in more time. In other words we can say that time complexity and space complexity tells us all about how efficient an algorithm.

Lets get started...

First of all lets look at what Binary Search does!

Process to search..

To search an element in a sorted array, here lets assume array is sorted in ascending order.

1. We find the middlemost element of an array lets say a[i] (Here 'a' is an array and 'i' refers to index number).

2. Check whether a[i] is greater then or less than the element to be searched for.

a. If a[i] == val, then we just found out the value....

b. Else if a[i] > val, then discard the remaining array after the middle element.

c. Else if a[i] < val, then discard the array beforehand the middle element.

Fig (a)

Above two points can be considered as the main logic in Binary Search. Now we are good start.

Now lets see how it actually works.

Starting with our function, we will create a function named Binary Search and declare the variables needed.

int BinarySearch( int n, int a[], int val)

Here, n = number of array elements

a[] = given array

val = value to be searched for in the array

Now we will write the body of the function of BinarySearch ().

  int first=0,mid,last=(n-1),val;

Here we declared two variables named 'first' and 'last' and then we stored the first and the last index value of the array 'a[]' respectively in those variables.

How to find the middle element?

We will use the formula mid = first + (last-first)/2

  mid=first+(last-first)/2;

This is because the above formula proves to be more reliable the the formula
mid=(first+last)/2

Now to find the value in the array a[], we will look for three conditions on the basis of the value of middle element

//One
    if(val==a[mid])
       {
           return mid;
       }

In 'one' we get our middle element.

//Two 
    else if(val>a[mid])
       {
           first=mid+1;
       }

In 'two' if value is greater than middle element, we eliminate the leftmost array from the middle element along with middle element.

In fig (a), the array elements 1, 2, 3 and 4 will be eliminated and now on wards our new array elements will be 5, 6, 7 with indices 4, 5, 6.

//Three 
    else
       {
           last=mid-1;
       }

In 'three' if value is less than the middle element, we will eliminate the rightmost array from the middle element along with middle element.

In fig (a), the array elements 4, 5, 6 and 7 will be eliminated and now on wards our new array elements will be 1, 2, 3 with indices 0, 1, 2.

Here our while loop gets completed.

  while(first<=last)
    {
       mid=first+(last-first)/2;
       if(val==a[mid])
       {
           return mid;
       }
       else if(val>a[mid])
       {
           first=mid+1;
       }
       else
       {
           last=mid-1;
       }  
   }

Now we will basically return -1 if any of the conditions in the above loop does not come out to be true.

Here's the complete function.

int BinarySearch(int a[], int n, int val)
{
    int first=0,mid,last=(n-1),val;

    while(first<=last)
    {
       mid=first+(last-first)/2;
       if(val==a[mid])
       {
           return mid;
       }
       else if(val>a[mid])
       {
           first=mid+1;
       }
       else
       {
           last=mid-1;
       }
     }
   return -1;
}

Know This!

Thursday, December 10, 2020

Binary Search Algorithm