Open In App

C++ Program For Linear Search

Last Updated : 23 Jul, 2025
Suggest changes
Share
Like Article
Like
Report

Linear search algorithm is the simplest searching algorithm that is used to find an element in the given collection. It simply compares the element to find with each element in the collection one by one till the matching element is found or there are no elements left to compare.

In this article, we will learn about linear search algorithm and how to implement it in C++.

Linear Search Using Library Function

C++ STL provides the std::find() function that implements the linear search algorithm to find an element in some container or array. This function returns the pointer/iterator to the element if found, otherwise, it returns the pointer/iterator to the end.

Note: std::find() function performs linear search with arrays, vectors and lists. For ordered and unordered data containers such as map, unordered_map, etc. it searches for the given element according to the search performance of the container.

C++ 
// C++ program to implement linear search using // std::find() function #include <bits/stdc++.h> using namespace std; int main() {  vector<int> v = {1, 2, 3, 4, 5, 8, 9, 11};  // Element to be searched  int key = 8;  // Searching for key in the vector v  auto it = find(v.begin(), v.end(), key);  // Checking if element is found or not  if (it != v.end())  cout << key << " Found at Position: " <<  it - v.begin() + 1;  else  cout << key << " NOT found.";  return 0; }

Output
30 Found at Position: 3

Time Complexity: O(n), where n is the number of elements
Auxiliary Space: Implementation defined, discussed below

Manually Implement Linear Search in C++

We can also manually implement the linear search in C++ by using both iteration and recursion. But first, we need to understand the working of linear search:

Working of Linear Search

The working of linear search is simple. We compare the element to find with each element in the given collection one by one starting from the first element. If the element is found, we return its index and stop the search. Otherwise, if we reach the end of the collection without finding the element, we return some other value denoting that the element is not found in the given collection.

Iterative Implementation

C++ 
// C++ Program to implement linear search  // algorithm iteratively #include <bits/stdc++.h> using namespace std; int linearSearch(vector<int> v, int key) {    // We test all the elements of the vector  // v against the given key  for (int i = 0; i < v.size(); i++) {    // If the KEY IS FOUND  if (v[i] == key) {  return i;  }  }    // Return some value denoting KEY NOT FOUND  return -1; } int main() {  vector<int> v = {1, 2, 3, 4, 5, 8, 9, 11};    // Value to search  int key = 8;  // Searching the key in the vector v  int i = linearSearch(v, key);    // Checking if element is found or not  if (i != -1)  cout << key << " Found at Position: " <<  i + 1;  else  cout << key << " NOT found.";  return 0; }

Output
6

Time Complexity: O(n), where n is the number of elements
Auxiliary Space: O(1)

Recursive Implementation

C++ 
// C++ Program to implement linear search using // recursion #include <bits/stdc++.h> using namespace std; int linearSearch(vector<int>& v, int key, int i) {    // If we have traversed the entire vector  // and the key is not found  if (i == v.size()) {  return -1;  }    // If the current element matches the key  if (v[i] == key) {  return i;  }  // Recursive call to check the next element  return linearSearch(v, key, i + 1); } int main() {  vector<int> v = {1, 2, 3, 4, 5, 8, 9, 11};    // Value to search  int key = 8;  // Searching the key in the vector v  int i = linearSearch(v, key, 0);    // Checking if element is found or not  if (i != -1) {  cout << key << " Found at Position: "  << i + 1;  } else {  cout << key << " NOT found.";  }    return 0; }

Output
8 Found at Position: 6

Time Complexity: O(n), where n is the number of elements
Auxiliary Space: O(n), for recursion stack.


K
kartik
Article Tags :

Explore

Lightbox