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)

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)

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.

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

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

advertisement
   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 Reference 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
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn