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 if key element exists in the given array or not. Here 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.

Also read – binary search program java

For example, let’s say, we have a key, that is, the number we are going to search in the array. Next we see if any index of the array is equal to the key.

If it is true we increment the count. Imagine we have an array,

Now, if key is 2, the system will search from the zeroth index. Search starts from first position, 2 is not equal to 1 so it goes to the next number.

If the key element is found, it will return the index position of the array element else it will return -1.

Now 2 is equal to 2, next the counter will increment 2 by 1. Now 2 is not equal to 3. At this stage system 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 n, int x) 
   { 
      for(int a = 0; a < n; 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 len = arrNum.length;
      System.out.println(key + " is found at index : " + search(arrNum, len, key)); 
   }
}

Output:

55 is found 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,

This is a five element array. I am going to find key element 2 in this particular array. It might be possible that with this array there may be two possible conditions which is, one is best case then 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 out 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 only 1 second just to find out key element 2 in the above array.

But in case if you don’t find out key element 2 in an array throughout 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 out 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 location and it will count it as 2.

Then it will move to the next position, then to next and next….. This is how we are working on linear search algorithm. But 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 out key element 2 we have to compare with each and every element present in the 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.