C Program to Implement Linear Search using Recursion

«
»

This is a C Program to implement Linear Search Algorithm using Recursion.

Problem Description

We have to create a C Program which finds the position of an element in an array using Linear Search Algorithm using Recursion.

Expected Input and Output

1. Average Case : On an average, linear search takes O(n) comparisons to find the position of the element. For example:

advertisement
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)

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

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)

advertisement
Problem Solution

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.

Program/Source Code

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.

  1. /* C Program to implement Linear Search Algorithm recursively */
  2.  
  3. #include <stdio.h>
  4. int RecursiveLS(int arr[], int value, int index, int n)
  5. {
  6.     int pos = 0;
  7.  
  8.     if(index >= n)
  9.     {
  10.         return 0;
  11.     }
  12.  
  13.     else if (arr[index] == value)
  14.     {
  15.         pos = index + 1;
  16.         return pos;
  17.     }
  18.  
  19.     else
  20.     {
  21.         return RecursiveLS(arr, value, index+1, n);
  22.     }
  23.     return pos;
  24. }
  25.  
  26. int main()
  27. {
  28.     int n, value, pos, m = 0, arr[100];
  29.     printf("Enter the total elements in the array  ");
  30.     scanf("%d", &n);
  31.  
  32.     printf("Enter the array elements\n");
  33.     for (int i = 0; i < n; i++)
  34.     {
  35.         scanf("%d", &arr[i]);
  36.     }
  37.  
  38.     printf("Enter the element to search  ");
  39.     scanf("%d", &value);
  40.  
  41.     pos =  RecursiveLS(arr, value, 0, n);
  42.     if (pos != 0)
  43.     {
  44.         printf("Element found at pos %d ", pos);
  45.     }
  46.     else
  47.     {
  48.         printf("Element not found");
  49.     }
  50.     return 0;
  51. }
Program Explanation

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.

Runtime Test Cases

Test case 1 – Average case (Element to be searched is at random location in the array).

advertisement
   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.

advertisement

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.