Linear search in java

Let’s learn linear search in java.

Linear search in java

Linear search java is very simple sequential search algorithm. It’s used to search key element exists in the given array or not.

Here search starts from leftmost element of an array and key element is compared with every element in an array.

Also read – binary search

Search continues until the key element is found. If key element is found,  index position is returned, else, -1 is returned.

Linear search is rarely used because it is practically very slow compared to binary search and hashing.

Let’s see java program for linear search,

public class LinearSearchDemo 
{
   // here function returns index of element x in arrLinear 
   static int searchNumber(int arrLinear[], int n) 
   {
      int num = arrLinear.length; 
      for(int a = 0; a < num; a++) 
      { 
         // here we are returning the index of the element if found
         if(arrLinear[a] == n) 
            return a; 
      }
      // here we are returning -1 if element is not found 
      return -1; 
   }

   public static void main(String[] args) 
   {
      int arrNum[] = {15, 25, 35, 55, 75, 95}; 
      int key = 55;
      int output = searchNumber(arrNum, key);
      if(output == -1)
      {
         System.out.print("Sorry!!Element is not present");
      }
      else
      {
         System.out.print("Element is present at index " + output);
      } 
   }
}

Output:

Element is present at index 3

What is time complexity of linear search?

In general we can say, if we have “n” elements in an array to search an element in an array, it will take order of n time, that is, O(n).

Also read – sparse matrix java

Using recursion

Now let’s learn linear search using recursion. Here user enters elements or integer numbers into the array using nextInt() method of Scanner class.

First we have to read length of given array and then read key value. Now we have to pass integer numbers, length and key value to linearRecursion() method.

linearRecursion() returns index value. If index is not equal to -1 then key is found at index + 1 else key does not exist in array.

Let’s see linear search in java using recursion,

import java.util.Scanner;

public class LinearSearchDemo 
{
   int linearRecursion(int[] arrNumber, int start, int last, int k)
   {
      if(last < start)
         return -1;
      if(arrNumber[start] == k)
         return start;
      return linearRecursion(arrNumber, start + 1, last, k);
   }

   public static void main(String[] args)
   {
      LinearSearchDemo obj = new LinearSearchDemo();
      int a, l, key, array[];
      Scanner sc = new Scanner(System.in);
      System.out.println("Please enter array length: ");
      l = sc.nextInt();
      array = new int[l];
      System.out.println("Please enter " + l + " elements");
      for(a = 0; a < l; a++)
      {
         array[a] = sc.nextInt();
      }
      System.out.println("Enter the search key value: ");
      key = sc.nextInt();
      int index = obj.linearRecursion(array, 0, l - 1, key);
      if(index != -1)
      {
         System.out.println(key + " is found at location " + (index + 1));
      }
      else
      {
         System.out.println(key + " doesn't exist in array.");
      }
      sc.close();
   }
}

Output:

Please enter array length: 6
Please enter 6 elements
15 25 35 55 75 95
Enter the search key value: 95
95 is found at location 6

Please enter array length: 6
Please enter 6 elements
15 25 35 55 75 95
Enter the search key value: 6
6 doesn’t exist in array.

Linear search string array java

Here let’s learn linear search of string array,

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class LinearSearchString 
{
   public void stringLinearSearch(String[] str, String strSearch)
   {
      int a;
      int flag = 0;
      for(a = 0; a < 5; a++)
      {
         if(strSearch.equals(str[a]))
         {
            flag = 1;
            break;
         }
      }
      if(flag == 1)
      {
         System.out.println("Word found at position: " + (a + 1));
      }
      else
      {
         System.out.println("Word not found");
      }
   }

   public static void main(String[] args) throws IOException 
   {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      LinearSearchString obj = new LinearSearchString();
      System.out.println("Please enter any 5 words: ");
      String[] strInput = new String[5];
      for(int a = 0; a < 5; a++)
      {
         strInput[a] = br.readLine();
      }
      System.out.println("Please enter word to be searched - ");
      String search = br.readLine();
      obj.stringLinearSearch(strInput, search);
   }
}

Output:

Please enter any 5 words:
ajinkya
virat
dhoni
zaheer
bhuvi
Please enter word to be searched – dhoni
Word found at position: 3

Please enter any 5 words:
ajinkya
virat
dhoni
zaheer
bhuvi
Please enter word to be searched – rahul
Word not found