Friday, 10 March 2017

C++ Program for Implementation of Exponential Search Algorithm

Like Binary search, Jump Search, Exponential search Algorithm can be only use in linear sorted array or list. This algorithm is better than Linear search and jump but equivalent to Binary search algorithm as it also works in O(log(n)) time.

But this algorithm can be very useful in a situation in which the array or list is verly large or infinte and if we don't know the range of indexes in which element can be present.

This Algorithm consist of two steps:

1. In first, step we will find the range where element can be present.
2. We will do Binary Search in above founded range.

How it works:


Approach is simple, we will start with subarray size 1 and compare its last element with the y (element to be found), then if the element y is greater than the last element of subarray we will continue by setting counter to 2*i.

If element is less than the last element of the subarray then we will implement binary search between the first and last element of the subarray.

Example:
         
          A[]={ 2, 4, 5 , 8, 45, 90, 98}

          set i=1

          Let element to be fount = x = 45

          Now,

          Pass 1 : i=1:   arr[1]=2 < 45
                                 therefore, set i=i*2
          Pass 2 : i=2:   arr[2]=5 < 45
                                 therefore, set i=i*2
          Pass 3 : i=4    arr[4]=45 = 45
                                 return True


          Algorithm will go on like this until last element of subarray is greater than  y (element to be found)


C++ Program for Implementation of Exponential Algorithm is given below:


PROGRAM:
 
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int find_element(int element);
int min(int i,int j);
int binary_search(int element,int beg,int end);
int arr[MAX],n;
int main()
{
    int i,result,element;
    printf("\nEnter the number of elements: ");
    scanf("%d",&n);
    printf("\nEnter the elements of the array: \n");
    for(i=0;i<n;i++)
    {
          scanf("%d",&arr[i]);
    }
       printf("\nEnter the element you want to search: ");
       scanf("%d",&element);
       result=find_element(element);
       if(result==-1)
       {
             printf("\nElement is not present in the array !") ;
       }
       else
       {
             printf("\n\nThe element %d is present at index %d",element,result);
       }
       return 0;
}
int find_element(int element)
{
    int result;
    int i=1;
    if(arr[0]==element)
    {
          return 0;
    }
    else
    {
          while(arr[i]<=element && i<n)
          {
             i=i*2;
          }
    }
    return binary_search(element,i/2,min(i,n));
  
}
int binary_search(int element,int beg,int end)
{
       int mid;
       mid=(beg+end)/2;
    while(beg<=end)
    {
              if(arr[mid]==element)
              {
                    return mid;
              }
              else
              {
                     if(arr[mid]<element)
                     {
                             beg=mid+1;
                     }
                     else
                     {
                             end=mid-1;
                     }
                     mid=(beg+end)/2;
              }
    }
    return -1;
}
int min(int i,int j)
{
    if(j>i)
         return i;
    else
         return j;
}
OUTPUT:


Implementation of Jump Search Algorithm 

Jump Search Algorithm Explanation 


EmoticonEmoticon