C++ Program to Implement Linear Search
Posted by Superadmin on August 08 2022 05:51:23

C++ Program to Implement Linear Search

Method 1: Implement Linear Search Algorithm

Problem Description

We have to write a C++ Program that finds the position of an element in an array using a Linear Search Algorithm. Create a separate function for linear search and then call it using an object.

Expected Input and Output

Case 1. Best Case: When the element to be searched is the first element of the array.
For example:

If the input array is {4, 6, 1, 2, 5, 3}
and the element to be searched is 4,
then the output will be Position: 1

Best Case time complexity: o(1)

Case 2. Average Case: When the element to be searched is any random element in an array.
For example:

If the input array is {66, -3, 31}
and the element to be searched is 31,
the output will be Position: 3

Average Case time Complexity: O(n)

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

Case 3. Worst Case: When the element to be searched is absent.
For example:

If the input array is {1, 3, 6, 1, 9}
and the element to be searched is 10,
then the output will be "Element not present".

Worst Case time complexity: O(n)

Problem Solution

We first have to create an array of numbers by taking input from the 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. 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 the element which was searched.

Check this: Programming MCQs | Computer Science Books

Program/Source Code

Here is the source code of the C++ Program to find the position of an element requested by the user using Linear Search Algorithm. 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 input N numbers and store them in an array.

 * Do a linear search for a given key and report success

```
 * or failure.
```
```
 */
```
```
#include <iostream>
```
```
using namespace std;
```
```
class LS
```
```
{
```
```
    public:
```

        void LinearSearch(int arr[], int value, int i, int n)

```
        {   int found = 0;
```
```
            for (i = 0; i < n ; i++)
```
```
            {
```
```
                if (value == arr[i] )
```
```
                {
```
```
                    found = 1;
```
```
                    break;
```
```
                }
```
```
            }
```
```
            if (found == 1)
```
```
            {
```

                cout<<"Element is present in the array at position   "<<i+1;

```
            }
```
```
            else
```
```
            {
```

                cout<<"Element is not present in the array.";

```
            }
```
```
        }
```
```
};
```
```
int  main()
```
```
{  int num;
```
```
    int i,  keynum, found = 0;
```

    cout<<"Enter the number of elements   ";

```
    cin>>num;
```
```
    int array[num];
```

    cout<<"Enter the elements one by one \n";

```
    for (i = 0; i < num; i++)
```
```
    {
```
```
        cin>> array[i];
```
```
    }
```

    cout<<"Enter the element to be searched   ";

```
    cin>>keynum;
```
```
    /*  Linear search begins */
```
```
    LS l1;
```

    l1.LinearSearch(array,keynum,i,num);

```
    return 0;
```
```
}
```

Program Explanation

1. Here in this program we have taken the array as an input from the user along with the key to be searched. We have created a separate function for Linear Search.
2. When the function is called we have to run a loop n times where n is the number of elements in an array.
3. In each iteration we are comparing the value of key with elements of array in increasing order of array index.
4. If key is equal to one of the array elements we print the value of index at which we found them to be equal.

Runtime Test Cases

1. Enter the number of elements   6
   Enter the elements one by one
   4
   6
   1
   2
   5
   3
   Enter the element to be searched   4
   Element is present in the array at position   1
 
2. Enter the number of elements   3
   Enter the elements one by one
   66
   -3
   31
   Enter the element to be searched   31
   Element is present in the array at position   3
 
3. Enter the number of elements   5
   Enter the elements one by one
   1
   3
   6
   1
   9
   Enter the element to be searched   10
   Element is not present in the array.

Method 2: Find element in a vector using Linear Search Algorithm

This C++ Program implements a linear search algorithm. The program takes in the number of elements of the vector of integers, takes the elements as input, takes in the element to be searched and goes through every element until the required element is reached.

Here is source code of the C++ program which implements linear search algorithm.

```
/*
```

 * C++ Program to Implement Linear Search Algorithm

```
 */
```
```
#include <iostream>
```
```
#include <vector>
```
```
 
```
```
/* Function to fill Vector */
```
```
void make_vector(std::vector<int>& v)
```
```
{
```
```
    int num, val;
```
```
 
```

    std::cout << "Enter the number of elements in vector ";

```
    std::cin >> num;
```
```
    for (int i = 0; i < num; i++)
```
```
    {
```
```
        std::cin >> val;
```
```
        v.push_back(val);
```
```
    }
```
```
}
```
```
 
```
```
/* Linear Search Function */
```

int lin_search(std::vector<int> v, int val)

```
{
```
```
    int key = -1;
```
```
    for (int i = 0; i < v.size(); i++)
```
```
    {
```
```
        if (v[i] == val)
```
```
        {
```
```
            key = i;
```
```
            break;
```
```
        }
```
```
    }
```
```
    return key;
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int key, val;
```
```
    std::vector<int> v;
```
```
 
```
```
    make_vector(v);
```
```
    std::cout << "Enter the number : ";
```
```
    std::cin >> val;
```
```
    key = lin_search(v, val);
```
```
    if (key != -1)
```

        std::cout << "\nElement " << val

                  << " is at position " << ++key;

```
    else
```

        std::cout << "\nElement " << val

```
                  << " is not present";
```
```
}
```

$ g++ main.cpp
$ ./a.out
Enter the number of elements in vector 5
2 4 10 23 32
Enter the number : 4
Element 4 is at position 2