Linear Search Algorithm

In this article we are going to learn about Linear Search Algorithm. First we will know What is Linear search algorithm, its definition and a simple example of linear search. Then we will see the Pseudocode for linear search algorithm and finally we will see a simple linear search algorithm program in java. Also, at the end I will specify the Worst, Average and Best Time complexity for the linear search algorithm.


What is Linear Search?

Linear Search is the simplest searching algorithm to find an element in a list of elements. Linear Search is used commonly for solving many search problems due to its simplicity of implementation.

When the list is small and unsorted Linear Search is preferred over the Binary Search due to its simplicity and speed.


Linear Search Algorithm Definition

According to Wikipedia Linear Search is defined as follows:

"In computer science, linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched."

So in simple words, linear search searches for a target element from the start of a list until the element is found or the end of the list is reached.

Linear Search Example

Consider we have an array: A = [4, 10, 6, 8, 3];

Now if we want to search for the number 6, then linear search starts its search from the the beginning of the array (1st element: 4). Since 4 is not equal to 6, the search continues to the next position (2nd element: 10). Again since 10 is not equal to 6, the search again advances to next element (3rd element: 6). Since the 3rd element 6 is equal to our target element 6, the search stops with a success. But in case the target number (eg. 15) is not present in the array then the search would reach the last element and will stop without success.


Linear Search Algorithm

We will first see the Pseudocode for linear search algorithm and then see a simple program in java.

Linear Search Algorithm Pseudocode

A very simple Pseudocode for linear search. Here A is the array of elements and target is the element to be searched.

LINEAR-SEARCH(A, target)
 for i=1 to A.length
    if A[i] == target
        print element found at i index
    end if
 end for

Linear Search Algorithm in Java

import java.util.*;

class LinearSearch
{
  public static void main(String[] args)
  {
    int i, target;
    int A[] = {4, 10, 6, 8, 3};

    Scanner sc = new Scanner(System.in);

    System.out.print("Enter number to find: ");
    target = sc.nextInt();

    for (i = 0; i < A.length; i++)
    {
      if (A[i] == target)
      {
        System.out.print("Element found at: " + i + " index");
        break;
      }

    }

    // if i == lenght of array means element was not found
    if (i == A.length)
    {
        System.out.print("Element not found");
    }

  }
}

Also you can implement it using a function as:

import java.util.*;

class LinearSearch
{
  public static void main(String[] args)
  {
    int target;
    int A[] = {4, 10, 6, 8, 3};

    Scanner sc = new Scanner(System.in);

    System.out.print("Enter number to find: ");
    target = sc.nextInt();

    if (linearSearch(A, target) == -1)
    {
      System.out.println("Element not found");
    }
    else
    {
      System.out.println("Element found at: " + linearSearch(A, target) + " index");
    }

  }

  public static int linearSearch(int A[], int target)
  {
    for (int i = 0; i < A.length; i++)
    {
      if (A[i] == target)
      {
        // return array index of element if found in array
        return i;
      }
    }

    // return -1 if element not found
    return -1;
  }

}

Compile and run program:

$ javac LinearSearch.java

$ java LinearSearch

Output:

$ java LinearSearch
Enter number to find: 6
Element found at: 2 index

$ java LinearSearch
Enter number to find: 21
Element not found

Linear Search Time Complexity

Time compexity for linear search algorithm

Worst Case Average Case Best Case
O(n) O(n) O(1)

The worst time complexity of the linear search algorithm is therefore O(n) as each element in an array is compared only once.


From this post we learned

  • What is Linear Search Algorithm
  • Pseudocode for Linear Search Algorithm
  • Linear Search Program in Java
  • Time Complexity of Linear Search Algorithm

Also check out my post on Binary Search Algorithm


Tags: