 # Recursive program for Linear search

### What is linear search :

Before writing the program of Linear search first we have to understand what is Linear search. Liner search is a searching algorithm in which we search an element linearly (from starting to end of the list ).we start the searching of element from  index  0 to until we get that element . If the element is found in the list then return the index of the element otherwise return -1 . so the time complexity of the linear search is depend on the number of elements in the list .

Time Complexity of the linear search:-

Best case:- In best case element will found at the index 0 . So the time complexity in best case is O(1).

Avg case :- In this time complexity is O(n). where n is number of element in the list.

Worst case: in this case element is not present in the list or at the last index of the list so we have to traverse whole list so the time complexity in this case is O(n)

Recurrence relation of Linear search:-

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

## Recursive Program of Linear search :-

```#include<stdio.h>

// recursive function of Linear search
int  Linersearch(int a[],int l,int r,int key)
{
if(l<r)
{
if(a[l]==key)
return l;
l++;
Linersearch(a,l,r,key);
}
else
return -1;
}

int main()
{
int n,key;
printf("Enter the lenght of the arary\n");
scanf("%d",&n);
int a[n];
printf("Enter the element of the array\n");
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("Enter the element which you want to search\n");
scanf("%d",&key);
int ans=Linersearch(a,0,n-1,key);
if(ans==-1)
printf("Element is not present in the array\n");
else
printf("Element is found at index %d",ans);
return 0;
}
```

Output:-

```Enter the length of the array
5
Enter the element of the array
1 4 3 2 5
enter the element which you want to search
4
Element found at index 1```

Also check this:-