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
Users Online
· Members Online: 0
· Total Members: 188
· Newest Member: meenachowdary055
Forum Threads
Latest Articles
Articles Hierarchy
C++ Program to Implement Linear Search
C++ Program to Implement Linear Search
Method 1: Implement Linear Search Algorithm
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.
Case 1. Best Case: When the element to be searched is the first element of the array.
For example:
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)
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)
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.
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;
-
}
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.
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
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