Linear Search in C++

Linear Search in C++

Linear Search in C++ is one of the simplest and easiest searching techniques used in programming. It helps you find a specific value in a list or an array by checking each element one by one from the beginning. If the value is found, it returns the position; if not, it tells you the element doesn’t exist.

Linear search is one of the simplest algorithms of data structure.

  • The element to be searched is compared with every element of the list one by one
  • Until the element that is to be searched is found.
  • If the element is not found till the end this means that the element is not present in the list. 
Linear Seach Algorith in C++

Algorithm to implement linear search in C++

Linear Search is a simple algorithm used to find an element in a list by checking each element one by one. Algorithm to implement Linear Search in C++:

  1. Read the item to be searched by the user. 
  2. Compare the search element with the first element in the list.
  3. If they both matches,  terminate the function.
  4. Else compare the search element with the next element in the list.
  5. Repeat steps 3 and 4 until the element to be search is found.
Time ComplexityO(n)
Best CaseO(1)
Worst CaseO(n)
Space ComplexityO(1)
Avg. Comparisons(n+1)/2
Linear Search in C++
Linear Search in C++

Program to implement linear search algorithm in C++

Iterative Method:

Run

#include<iostream>
using namespace std;

void LinearSearch(int arr[], int len, int item){

    for(int i=0;i<len;i++){
        if(arr[i] == item){
            cout << item << " Found at index : " << i;
            return;
        }
    }
    cout << "Not found";
    
}

int main() {
    int arr[] = {10, 5, 15, 21, -3, 7};
    
    // calculating length of array
    int len = sizeof(arr)/sizeof(arr[0]);
    
    // item to be searched
    int item = 21;
    LinearSearch(arr, len, item);

    return 0;
}
// space complexity: O(N)
// time complexity : O(N)

Output:

21 Found at index : 3

Method 2 (Using Recursion)

This method uses recursion in c++ :

Run
// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
#include<iostream>
using namespace std;

int LinearSearch(int arr[], int index, int item)
{
    if(arr[index] == item)
        return index;
    else if (index == -1)
        return -1;
    
    return LinearSearch(arr, index - 1, item);
}

int main() 
{
    int arr[] = {10, 5, 15, 21, -3, 7};

    // calculating length of array 
    int len = sizeof(arr)/sizeof(arr[0]);

    // item to be searched
    int item = 21;
    
    int index = LinearSearch(arr, len - 1, item);

    if(index >= 0)
        cout << "Item found at index: " << index;
    else
        cout << "Item not found";
        
    return 0;
}

Output

Item found at index: 3
Linear search in C++ Meme

Method 3 : Linear Search Using STL (std :: find)

Algorithm

  • Start
  • Input the size of the array (n)
  • Input the array elements
  • Input the key to search
  • Use std::find from <algorithm> header to search for the key in the array
  • If iterator returned by std::find is not equal to arr + n,
    → Element is found, print index
  • Else
    → Element is not found
  • End

Run

#include <iostream>
#include <algorithm> // for std::find
using namespace std;

int main() {
int n, key;
cout << "Enter the size of the array: ";
cin >> n;

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

cout << "Enter the element to search: ";
cin >> key;

// Using std::find to perform linear search
auto it = find(arr, arr + n, key);

if (it != arr + n) {
cout << "Element found at index " << (it - arr) << endl;
} else {
cout << "Element not found in the array." << endl;
}

return 0;
}

Sample Output:

Enter the size of the array: 5
Enter the elements of the array:
10 20 30 40 50
Enter the element to search: 30
Element found at index 2

Explanation:

  • std::find(start_ptr, end_ptr, key) returns an iterator pointing to the first occurrence of key if found.
  • If the key is not found, it returns end_ptr.
  • Subtracting the base pointer (arr) from the iterator gives the index of the found element.

Linear search and Binary Search Comparison

  • Linear search (Time complexity): O(n)
  • Binary search (Time complexity): Log(n)

Examples of Linear Search in C++

Example 1: Linear Search in a Static Integer Array (Iterative Method)

This example demonstrates how to implement linear search using a simple for loop. The array is predefined (static), and we look for a specific integer value by comparing each element one by one.

Code:

#include <iostream>
using namespace std;

int main() {
int arr[] = {4, 15, 7, 23, 11};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 23;
bool found = false;

for (int i = 0; i < n; i++) {
if (arr[i] == key) {
cout << "Element found at index " << i << endl;
found = true;
break;
}
}

if (!found)
cout << "Element not found" << endl;

return 0;
}

Output:

Element found at index 3

Explanation:

  • We search for 23 in a hard-coded array using a loop.
  • Once found, it prints the index and exits early.

Example 2: Linear Search in a Vector of Strings (Using std::find)

In this example, we use the Standard Template Library (STL) function std::find to search for a string in a vector. This method simplifies the code and works well with C++ containers like vectors.

Code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
vector<string> fruits = {"apple", "banana", "mango", "grape", "kiwi"};
string key = "mango";

auto it = find(fruits.begin(), fruits.end(), key);

if (it != fruits.end()) {
cout << "Fruit found at index " << (it - fruits.begin()) << endl;
} else {
cout << "Fruit not found" << endl;
}

return 0;
}

Output:

Fruit found at index 2

Explanation:

  • Searches for “mango” in a vector of strings using std::find.
  • It prints the index if found.
Quiz time

Fun Fact!

Quiz time

About Linear Search

We follow linear search in our daily life while finding a specific book, medicine or movie in stores.

Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place.

The only thing you know about the ride is the license plate number. How do you find your Uber ride?

The obvious thing is to go to the parking lot and search all the cars one by one. This method of searching is called linear search, where we search for all possible options until we get our desired result.

Searching

Searching algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

FAQs

Linear Search is a simple method to find an element in a list or array. It checks each item one by one from the beginning until it finds the required value or reaches the end.

Use Linear Search when the data is unsorted or small in size. Binary Search only works on sorted data, but Linear Search does not require sorting.

Linear Search is slower compared to other searching methods like Binary Search, especially for large data. This is because it may need to check every element in the list.

Yes, Linear Search works with arrays, vectors, strings, and even custom objects. You can use a loop or built-in C++ functions like std::find from the STL.

The worst-case time complexity of Linear Search is O(n), where n is the number of elements. This means it may check every item once to find the result.