Linear search using recursion C code

 

Linear search using recursion C code

Linear search 

In linear search traverse data sequentially to locate ITEM so it called sequential search .Find ITEM in  in data where data contains n elements. Worst case occurs when must search through the entire array data. Algorithm require (n+1) comparisons. So running time proportional to n. To find the complexity of linear search use recurrence equation and solve using substitution method.

Recurrence equation of linear search to find the complexity of algorithm is

T(n)=T(n-1)+1

First find T(n-1)

T(n-1)=T(n-1-1)+1

T(n-1)=T(n-2)+1

put the value of T(n-1)

T(n)=T(n-2)+1+1

T(n)=T(n-2)+2

....

......

Repeat step k times get

T(n)=T(n-k)+k

if  n-k=0

    so k=n

put the value of k

T(n)=T(n-n)+n

T(n)=T(0)+n

T(n)=1+n

T(n)=O(n)

So complexity of linear search is O(n) by substitution method.

Recursive code of linear search is

void linearsearch(int a[],int lb,int ub,int item)

{

    if(ub<lb)

    printf("search unsucessful");

   else if(a[ub]==item)

    printf("search successful element found at  %d",ub);

    else

    linearsearch(a,lb,ub-1,item);

}

 C code of linear search algorithm using recursion

#include<stdio.h>

void linearsearch(int a[],int lb,int ub,int item);

void main()

{

    int n;

    int i;

    int a[10];

    int item;

    printf("enter total number of element");

    scanf("%d",&n);

    for(i=0;i<n;i++)

    {

        scanf("%d",&a[i]);

    }

    printf("enter item you want to search");

    scanf("%d",&item);

    linearsearch(a,0,n-1,item);

}

void linearsearch(int a[],int lb,int ub,int item)

{

    if(ub<lb)

    printf("search unsucessful");

   else if(a[ub]==item)

    printf("search successful element found at  %d",ub);

    else

    linearsearch(a,lb,ub-1,item);

}

Output

enter total number of element5 1 2 3 4 5 enter item you want to search5 search successful element found at 4