Linear search in java

by February 20, 2017 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.

linear search in java

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.

Also read – binary search java

Let’s see java program for linear search or linear search program using function.

public class LinearSearchExample
{
   // 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.println("Sorry!!Element is not present");
      }
      else
      {
         System.out.println("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).

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.

Also read – sparse matrix java

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 or linear search user input.

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