Linear Search in C++

Linear search or Sequential search in C++ | The Linear search or Sequential search is a method to finding an element within a given list or array. Linear search or Sequential search is usually very simple to implement and is practical when the list has only a few elements, or when performing a single search in an unordered list.

Example:-
Array = {50, 90, 30, 70, 60};

Input to Search = 30
Output:- 30 found at Index 2.

Input to Search = 10
Output:- 10 not found.

How Linear Search Works?

In Linear search, finds the index or location of search in the given array. It begins the search by comparing the search key and the first element of the array/list. If the first element is not equal to the search key then it will compare with the next element, and so on until the match is found or the end of the array. If the match is found then it returns its index, else it will reach the end of the array or list which means the search key is not available.

Let us understand it through an example:- Given array = {50, 90, 30, 70, 60};

Assume the search key = 30; Then traverse through the array and compare with each element. The first element of the array is 50, but 50 is not equal to 30 therefore move to the next element. The next element is 90, but it is also not equal to 30 therefore move to the next element. The next element of the array is 30 which is equal to the search key 30 therefore return the index of the current element of the array.

It was the situation where the search key exists in the array, now let us assume when the search key is not available. Assume the search key = 10. Traverse through the array and compare with each element. It won’t match with 50, 90, 30, 70, 60, and finally reached the end of the array. Therefore return -1 which means the search key is not available.

Linear Search Algorithm in C++

The procedure to find an element in a given array or list through linear search,
a) Take array, size of the array, and the search key. Assume they are:- array, n, and key
b) Traverse through the array.
c) Compare key with each element.
d) If the match is found then return the position.
e) Else repeat the process until the end of the array.
f) After traversing the array If the match is not found then return -1.

The algorithm for linear or sequential search can be given as,

linear search(array, n, key) {
    i = 0;
    while(i < n) {
       if(key == array[i])
          then return i;
       else
          i= i + 1;
    }
    return -1;  
}

Time complexity of the above algorithm:- O(n)

• Best case performance:- O(1). When the search key is present at first index/position of the array then only one comparision is required.
• Worst-case performance:- O(n). When the search key is present at the last index of the array then it requires N comparision, where N is the size of the array.

Linear Search Program in C++

Let us write a C++ program to search an element in an array using linear search. We will take the help of Function. The function is a small program is used to do a particular task. In C a big program divided into several small subroutines/functions/procedures.

#include<iostream>
using namespace std;
// function for linear search
/* if match found then return index of search key
   else return -1 */
int linearSearch(int arr[], int n, int key) 
{
  for(int i=0; i<n; i++) 
  {
    if(key == arr[i])
      return i;
  }
  return -1;
}
// main function
int main()
{
  int array[] = {50, 90, 30, 70, 60};
  int key = 0;

  // take key
  cout << "Enter Search Element: ";
  cin >> key;

  // find the size array
  int size = sizeof(array)/sizeof(array[0]);

  // search key
  int index = linearSearch(array, size, key);
  
  if(index == -1)
    cout << key << " Not Found" << endl;
  else
    cout << key << " Found at Index = " << index << endl;

  return 0;
}

Output:-

Enter Search Element: 10
10 Not Found

Enter Search Element: 70
70 Found at Index = 3

Enter Search Element: 60
60 Found at Index = 4

Enter Search Element: 90
90 Found at Index = 1

Using Recursion

A function that contains a call to itself is called the recursive function. A technique of defining the recursive function is called recursion. The recursive function allows us to divide the complex problem into identical single simple cases that can handle easily. This is also a well-known computer programming technique: divide and conquer. Let us write a C++ program to search an element in an array using linear search.

#include<iostream>
using namespace std;
// recursive function for linear search
/* if match found then return index of search key
   else return -1 */
int linear(int arr[], int n, int index, int key)
{
   if(index > n)
      return -1;
   else if (arr[index] == key)
      return index;
   else
      return linear(arr, n, index+1, key);
}
// main function
int main()
{
  int array[] = {50, 90, 30, 70, 60};
  int key = 0;

  // take key
  cout << "Enter Search Element: ";
  cin >> key;

  // find the size array
  int size = sizeof(array)/sizeof(array[0]);

  // search key
  int index = linear(array, size, 0, key);
  
  if(index == -1)
    cout << key << " Not Found" << endl;
  else
    cout << key << " Found at Index = " << index << endl;

  return 0;
}

Output:-

Enter Search Element: 30
30 Found at Index = 2

Enter Search Element: 60
60 Found at Index = 4

Enter Search Element: 999
999 Not Found

Improved Version

We get worst-case performance O(n) because we are comparing array elements only from one side. Instead of one side, if we compare the array elements from both ends i.e. from the front and last then it will reduce the number of iterations. Let us understand it through an example,

Array = {10, 20, 30, 40, 50};
Search key = 40;
In the first iteration, 40 is not equal to 10 (from the left side), and 40 is not equal to 50 (from the right side).
In the second iteration, 40 is not equal to 20 (from the left side), but 40 is equal to 40.
Therefore the search key found at index 3.

The normal linear search can find it in 4 iterations, but an improved linear search can find it in only 2 iterations.

C++ program for the above improved linear search,

#include<iostream>
using namespace std;
// function for improved linear search
/* if match found then return index of search key
   else return -1 */
int linearSearch(int arr[], int n, int key) 
{
  for(int i=0, j=n-1; i<=n/2; i++, j--) 
  {
    if(key == arr[i])
      return i;
    if(key == arr[j])
      return j;
  }
  return -1;
}
// main function
int main()
{
  int array[] = {50, 90, 30, 70, 60};
  int key = 0;

  // take key
  cout << "Enter Search Element: ";
  cin >> key;

  // find the size array
  int size = sizeof(array)/sizeof(array[0]);

  // search key
  int index = linearSearch(array, size, key);
  
  if(index == -1)
    cout << key << " Not Found" << endl;
  else
    cout << key << " Found at Index = " << index << endl;

  return 0;
}

Output:-

Enter Search Element: 60
60 Found at Index = 4

Enter Search Element: 90
90 Found at Index = 1

Enter Search Element: 0
0 Not Found

The best-case time complexity is the same as previous:- O(1)
The worst-case time complexity:- O(n/2)

Also See,

• Linear Search Algorithm in DSA
• C Program for Linear Search
• Java Program for Linear Search
• Python Program for Linear Search

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Search