Linear search

Linear search is one of the basic search techniques that we've now. Although this is not a very good search technique, one should understand this concept. Let's consider our aim to search for a key element in an array of elements. We loop through all the array elements and check for existence of the key element. Since we go element by element, this search is called as Linear search or sequential search. Search element is called as key element.

Linear search algorithm


 BEGIN
  DECLARE key, array, i, found
  ASSIGN values to array/ACCEPT array values
  PRINT "Please enter key element:"
  ACCEPT key
  ASSIGN i with 1
  FOR EACH i in 1 to array.length
  LOOP
   IF array[i] = key
   THEN
    ASSIGN found with true
   END IF
  END LOOP
  IF found = true
  THEN
   PRINT "Key found"
  ELSE
   PRINT "Key not found"
  END IF
 END

The above algorithm will search for a key even after key is found until all the array of elements are being checked. Once we identify the element, we don't need continue further. i.e.; we can break the loop and continue further. Here the Java program for the linear search

LinearSearch.java

/**
 * This class demonstrates the linear search.
 * @author SANTHOSH REDDY MANDADI
 * @version 1.0
 * @since 29 August 2012
 */

import java.io.*;

public class LinearSearch
{
  public static void main(String args[]) throws Exception
  {
    int values[] = {5, 16, 10, 17, 8, 25};
    int key;
    int i;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    System.out.println("Array values are:");
    for(int n:values)
    {
      System.out.print(n+"\t");
    }
    System.out.println("\nPlease enter a key (search) value:");
    key = Integer.parseInt(br.readLine());
    for(i=0; i< values.length; i++)
    {
      if(values[i] == key)
      {
        break;
      }
    }
    if(i==values.length)
    {
      System.out.println(key+" not found...!");
    }
    else
    {
      System.out.println(key+" found at position "+(i+1));
    }
  }
}
Explanation
  • Best case: if you run the above program to find a key element 5, program will execute the for loop only once since we're breaking the loop when element is found.

  • Worst case: if the key element is the last element, for loop has to be executed for 6 times (array length is 6) to identify the element.
Output

>java LinearSearch
Array values are:
5       16      10      17      8       25
Please enter a key (search) value:
16
16 found at position 2

>java LinearSearch
Array values are:
5       16      10      17      8       25
Please enter a key (search) value:
25
25 found at position 6

>java LinearSearch
Array values are:
5       16      10      17      8       25
Please enter a key (search) value:
5
5 found at position 1

>java LinearSearch
Array values are:
5       16      10      17      8       25
Please enter a key (search) value:
34
34 not found...!