Linear search java

Hey guys, Welcome to flower brackets blog, how are you doing? Today you will learn linear search java.

Linear search 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.

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.

Also read – binary search in java

Imagine we have an array and a key, that is, the number we are going to search in the array.

Now, if key element is 2, the system will search from 0th index. 2 is not equal to 1 so it goes to the next number.

Now 2 is equal to 2, next the counter will increment 2 by 1. Now 2 is not equal to 3. At this stage it has found the number 2.

Let’s see java program for linear search,

public class LinearSearchDemo 
{
   // here function returns index of element x in arrLinear 
   static int search(int arrLinear[], int x) 
   {
      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] == x) 
            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 = search(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?

Let us discuss about time complexity of linear search. Suppose I am going to find key element 2 in an array which is,

Here’s an array of five elements and I am going to find key element 2. It might be possible that with this array there may be two possible conditions which is, one is best case and the second is worst case.

In the best case scenario it might be possible that whichever element we are searching in an array might exist in the very first position of an array.

Also read – sort string array java

So, if you find key element 2 at the very first position, at that time the time complexity will be at the order of O(1). Because it took 1 second just to find key element 2 in the above array.

But in case if you don’t find key element 2 in an array even after traversing the array, that means, we are traversing 1, 2, 3, 4, 5 all the five elements and still the search is unsuccessful.

In that case, searching time will be at the order of O(n). It might also be possible that key element 2 maybe occurring in another position like this,

We cannot stop searching the element on this particular position. We first find the element at the very first time. It might be possible that this key element 2 might be occurring in other part of the array also.

So we are searching like this,

2 will be compared with 1. If it is matched then ok. If it does not match then we will move to the next element. Now, if the key element is matched then it will track the index position.

Then it will move to the next position, then to next and next….. we need to search key element 2 throughout the array or traversing the whole array.

Also read – sparse matrix java

So if above array of five elements is to find key element 2 we have to compare with each and every element present in an array. That means it is taking, say, five seconds of time.

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).

Because it is comparing single key element with each and every element in an array. This is all about the analysis of linear search.