## 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 LinearSearchArray values are:5       16      10      17      8       25Please enter a key (search) value:1616 found at position 2>java LinearSearchArray values are:5       16      10      17      8       25Please enter a key (search) value:2525 found at position 6>java LinearSearchArray values are:5       16      10      17      8       25Please enter a key (search) value:55 found at position 1>java LinearSearchArray values are:5       16      10      17      8       25Please enter a key (search) value:3434 not found...!`