Linear Search Technique

Home      

What is linear search technique and how to implement in java programming language?

Ans:-  Linear search algorithm finds given element in a list of elements with O(n) time complexity where n is total number of elements in the list. This search process starts comparing of search element with the first element in the list. If both are matching then results with element found otherwise search element is compared with next element in the list. If both are matched, then the result is "element found". Otherwise, repeat the same with the next element in the list until search element is compared with last element in the list, if that last element also doesn't match, then the result is "Element not found in the list". That means, the search element is compared with element by element in the list.

When data items are stored in a collection such as a list or array, we say that they have a linear or sequential relationship. Each data item is stored in a position relative to the others. In  lists, these relative positions are the index values of the individual items. Since these index values are ordered, it is possible for us to visit them in sequence. This process gives rise to our first searching technique, the sequential search or linear search.

Below figure shows how this search works. Starting at the first item in the list, we simply move from item to item, following the underlying sequential ordering until we either find what we are looking for or run out of items. If we run out of items, we have discovered that the item we were searching for was not present.

Linear search is implemented using following steps...

• Step 1: Read the search element from the user
• Step 2: Compare, the search element with the first element in the list.
• Step 3: If both are matching, then display "Given element found!!!" and terminate the function
• Step 4: If both are not matching, then compare search element with the next element in the list.
• Step 5: Repeat steps 3 and 4 until the search element is compared with the last element in the list.
• Step 6: If the last element in the list is also doesn't match, then display "Element not found!!!" and terminate the function.

Example

Consider the following list of element and search element...

Java Program to implement Linear search.

import java.util.Scanner;

public class LinearSearch {

public static void main(String[] args) {

int list[],size,i,sElement;

list=new int[20];

  Scanner sc=new Scanner(System.in);

  System.out.println("Enter size of the list: ");

   size=sc.nextInt();

  System.out.println("Enter any "+size+"integer values");

 

  for(i = 0; i < size; i++)

  list[i]=sc.nextInt();

  System.out.println("Enter the element to be Search: ");

  sElement=sc.nextInt();

  

  // Linear Search Logic

  for(i = 0; i < size; i++)

  {

     if(sElement == list[i])

     {

      System.out.println("Element is found at "+i+" index");

        break;

     }

  }

  if(i == size)

  System.out.println("Given element is not found in the list!!!");

}

}

Home