This is a C Program to implement Linear Search Algorithm using Recursion.
We have to create a C Program which finds the position of an element in an array using Linear Search Algorithm using Recursion.
1. Average Case : On an average, linear search takes O(n) comparisons to find the position of the element. For example:
If the input array has data as {4, 6, 1, 2, 5, 3} and element to be searched is 6, then the expected output will be Position 2
Average case time complexity : O(n)
2. Best Case: When the key we have to search is the first element of array, we have to make just one comparison. For example:
If the input array has data as {66, -3, 31} and element to be searched is 66 then the expected output will be Position 1
Best case time complexity : O(1)
3. Worst Case: When the key to be searched for is the last element of an array, the algorithm has to traverse the whole array element by element in order to look for the key. For example:
If the input array has data as {1, 3, 6, 1, 9} and element to be searched is 9 then the expected output will be Position 5
Worst case time complexity : O(n)
1. We first have to create an array of numbers by taking input from user.
2. We have to input an array of numbers and then apply the linear search algorithm to find the position of an element in an array, if it exists.
3. In order to look for an element in an array, we’ll go sequentially in increasing index values.
4. If we encounter the element requested by the user we will return the position of that element in array, but if it is not there we will return -1 which indicates the absence of element which was searched.
Here is the source code of the C Program to implement Linear Search Algorithm on array of numbers using recursion. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.
/* C Program to implement Linear Search Algorithm recursively */
#include <stdio.h>
int RecursiveLS(int arr[], int value, int index, int n)
{
int pos = 0;
if(index >= n)
{
return 0;
}
else if (arr[index] == value)
{
pos = index + 1;
return pos;
}
else
{
return RecursiveLS(arr, value, index+1, n);
}
return pos;
}
int main()
{
int n, value, pos, m = 0, arr[100];
printf("Enter the total elements in the array ");
scanf("%d", &n);
printf("Enter the array elements\n");
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
printf("Enter the element to search ");
scanf("%d", &value);
pos = RecursiveLS(arr, value, 0, n);
if (pos != 0)
{
printf("Element found at pos %d ", pos);
}
else
{
printf("Element not found");
}
return 0;
}
1. In Linear search, we search an element or value in a given array by traversing the array from the starting, till the desired element or value is found.
2. The array is searched sequentially and the position is returned if the key element to be searched is available in the array, otherwise “Element not found” is printed.
3. Here in this C Program we have created a recursive function called RecursiveLS(), which takes in 4 input parameters and returns the position of element in a array which is searched by the user.
4. If the element that is searched is the first we directly return the index.
5. But if it is not the first element of array, we decrease the size of array by 1, by eliminating the first element of the array, which means when the RecursiveLS() is called second time the array size will be (n-1). This will go on until the element is found.
Test case 1 – Average case (Element to be searched is at random location in the array).
Enter the total elements in the array 6 Enter the array elements 4 6 1 2 5 3 Enter the element to search 6 Element found at pos 2
Test case 2 – Best case (Element to be searched is at 1st position itself).
Enter the total elements in the array 3 Enter the array elements 66 -3 31 Enter the element to search 66 Element found at pos 1
Test case 3 – Worst case (Element to be searched is at the end of the array).
Enter the total elements in the array 5 Enter the array elements 1 3 6 1 9 Enter the element to search 9 Element found at pos 5
Sanfoundry Global Education & Learning Series – 1000 C Programs.
Here’s the list of Best Books in C Programming, Data-Structures and Algorithms
- Apply for Computer Science Internship
- Check Computer Science Books
- Watch Advanced C Programming Videos
- Check C Books
- Apply for C Internship