Linear Search in Java with Example

It is an algorithm that searches for an element one by one in an array, until the target element is found.

Consider if X is an element to be searched in an array, then linear search performs the following:

1. Compare X with each element of array one by one


2. If X matches with an element, return the index of array


3. If X doesn’t match with any of elements, return -1 which means element X not found

Implementation of Linear Search

public class LinearSearch{

   public static void main(String[] args){
      int arr[] = new int[]{1,2,3,4,5,6,7,8,9,10};   // array of elements
      int X = 9;   // element to search
  
      int xPos = linearSearch(arr, X);
      if(xPos != -1){
         System.out.println("Element found at postion:"+xPos);
      }else{
         System.out.println("Element not found");
      }
   }
 
   private static int linearSearch(int[] arr, int X){
      for(int index = 0; index < arr.length; index++){
         if(X == arr[index])   // Compare X with each element one by one
            return index;      // If element found, return index
         
      }
  
      return -1;   // If element not found, return -1
   }

}

In the above program, we have an array of elements arr[ ] and, where X is the element to be searched. The linearSearch(int[ ], int) method traverses the array elements each one by one and compares with target element X. If X is equal to any element then this method returns the index of the element. Else, if no element is equal to X then it returns -1 as the indication of element X is not found in the array. Thus, the linear search algorithm can be implemented to perform the search of an element in an array.

Time Complexity

The worst case of Linear Search algorithm is that every element must be compared to determine whether an element exists in an array or not. Consider if the array has 10 elements, then this algorithm requires up to 10 comparisons. For 100 elements, it requires up to 100 comparisons. For n number of elements it requires up to n comparisons. So, the number of comparisons required depends on the number of elements in an array and, as the n grows, the number of comparisons equally grows.

Hence, the Time Complexity for Linear Search is O(n).

Related Posts:

     Binary Search in Java with Example

• Data Structures
• Java