Linear Search

➤ Java Bean with Examples
➤ How to Code a Game
➤ Array Programs in Java
➤ Java Inline Thread Creation
➤ Java Custom Exception
➤ Hibernate vs JDBC
➤ Object Relational Mapping
➤ Check Oracle DB Size
➤ Check Oracle DB Version
➤ Generation of Computers
➤ XML Pros & Cons
➤ Git Analytics & Its Uses
➤ Top Skills for Cloud Professional
➤ How to Hire Best Candidates
➤ Scrum Master Roles & Work
➤ CyberSecurity in Python
➤ Protect from Cyber-Attack
➤ Solve App Development Challenges
➤ Top Chrome Extensions for Twitch Users
➤ Mistakes That Can Ruin Your Test Metric Program

Linear search or Sequential search in data structure | 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 in 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

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;  
}

The time complexity of the above algorithm:- O(n)

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

Program

Let us demonstrate a linear search program in the C programming language using function. 

#include <stdio.h>
// 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;

  printf("Enter Search Element: ");
  scanf("%d", &key);

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

  // search key
  int index = linearSearch(array, size, key);
  
  if(index == -1)
    printf("%d Not Found\n", key);
  else
    printf("%d Found at Index = %d\n", key, index);

  return 0;
}

Output:-

Enter Search Element: 30
30 Found at Index = 2

Enter Search Element: 10
10 Not Found

Enter Search Element: 60
60 Found at Index = 4

Let us demonstrate a linear search program in the C++ programming language. 

#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 = 70;

  // 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:-

70 Found at Index = 3

Let us see the linear search program in the Java programming language. 

public class Search {
   public static void main(String[] args) {

      int arr[] = { 50, 90, 30, 70, 60 }; // array
      int key = 70; // search key
      int size = arr.length; // size of array

      // linear search
      int index = linearSearch(arr, size, key);

      // display result
      if (index == -1)
         System.out.println(key + " not Found.");
      else
         System.out.println(key + " Found at Index = " + index);

   }

   // Method for linear search
   /* If match found then return index of search key
    * else return -1 */
   public static int linearSearch(int[] arr, int size, int key) {
      // traverse through the array
      for (int i = 0; i < size; i++) {
         if (key == arr[i])
            return i;
      }
      return -1;
   }

}

Output:-

70 Found at Index = 3

Let us see the program in Python. 

# Python program for linear search

def linearSearch(arr, key):  #user-defined function
    for i in range(len(arr)): 
        if (arr[i] == key): 
            return i 
    return -1

arr = [50, 90, 30, 70, 60]  #array
key = 70  #search key

index = linearSearch(arr, key) #calling function

# display result
if (index == -1):
    print(key, 'not Found.
else:
    print(key, 'Found at Index', index)

Output:-

70 Found at Index 3

Linear search is rarely used practically because other search algorithms such as the binary search algorithm and hash tables allow significantly faster-searching comparison to Linear search.

The main disadvantages of linear search are:-

  • It needs more space and time complexity.
  • If the key element is the last element and the search is from the first element then it is a worst-case. Similar if the key is at the first element and the search is from the last element then again it is a worst-case.

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 is found at index 3.

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

The algorithm for improved Linear Search can be written as,

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

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

C Program for the above improved linear search,

#include <stdio.h>
// 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, 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;

  printf("Enter Search Element: ");
  scanf("%d", &key);

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

  // search key
  int index = linearSearch(array, size, key);
  
  if(index == -1)
    printf("%d Not Found\n", key);
  else
    printf("%d Found at Index = %d\n", key, index);

  return 0;
}

Output:-

Enter Search Element: 70
70 Found at Index = 3

Q) Which of the following is a disadvantage of linear search?
a) Requires more space
b) Greater time complexities compared to other searching algorithms
c) Not easy to understand
d) All of these

Ans:- b) Greater time complexities compared to other searching algorithms.

Also See:-

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!

Leave a Comment

Your email address will not be published. Required fields are marked *