C++ Program to Implement Linear Search using Recursion
Posted by Superadmin on August 08 2022 05:56:34

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: When the element searched for is any random element in the array.

If the input array is {4, 6, 1, 2, 5, 3},
and the user has searched for 2
then the output will be Position: = 4

2. Best Case: When the element searched for is the first element of array.
For example:

If the input array is arr = {66, -3, 31},
and user has searched for 66,
then the output will be Position: = 1

3. Worst Case: When the element searched for is the last element of the array.
For example:

If the input array is {1, 3, 6, 1, 9}
and the user has searched for 9,
then the output will be Position: = 5

Problem Solution

1. We first have to create an array of numbers by taking input from user. 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.
2. In order to look for an element in an array, we’ll go sequentially in increasing index values. 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 source code of the C++ Program to implement Linear Search Algorithm 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 <iostream>
```
```
using namespace std;
```
```
class LS
```
```
{
```
```
public:
```

    int RecursiveLS(int arr[], int value, int index, int n)

```
    {
```
```
        int pos = 0;
```
```
        if(index >= n)
```
```
        {
```
```
            return 0;
```
```
        }
```
```
        if(arr[n-1] == value)
```
```
        {
```
```
            pos = n;
```
```
            return pos;
```
```
        }
```
```
        else if (arr[index] == value)
```
```
        {
```
```
            pos = index + 1;
```
```
            return pos;
```
```
        }
```
```
        else
```
```
        {
```

            return RecursiveLS(arr, value, index+1, n-1);

```
        }
```
```
        return pos;
```
```
    }
```
```
};
```
```
int main()
```
```
{
```
```
    LS l1;
```
```
    int n, value, pos, m = 0, arr[100];
```

    cout<<"Enter the total elements in the array  ";

```
    cin>>n;
```
```
    cout<<"Enter the array elements  ";
```
```
    cout<<endl;
```
```
    for (int i = 0; i < n; i++)
```
```
    {
```
```
        cin>>arr[i];
```
```
    }
```

    cout<<"Enter the element to search  ";

```
    cin>>value;
```

    pos =  l1.RecursiveLS(arr, value, 0, n);

```
    if (pos != 0)
```
```
    {
```

        cout<<"Element found at pos  "<<pos;

```
    }
```
```
    else
```
```
    {
```
```
        cout<<"Element not found";
```
```
    }
```
```
    return 0;
```
```
}
```

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. 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.
2. 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.
3. If the element that is searched is the first or the last element of the array, we directly return the index, but if it is not either of them we decrease the size of array by 2, by eliminating the first and last elements of the array, which means when the RecursiveLS() is called second time the array size will be (n-2).
4. This will go on till the element is found.

Runtime Test Cases

1. Enter the total elements in the array  6
   Enter the array elements
   4
   6
   1
   2
   5
   3
   Enter the element to search  2
   Element found at pos  4
 
2. 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
 
3. 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