> DSA > Linear Search

Linear Search Algorithm in Java

Last Updated: 06 October, 2024 🕓 5 Mins

Introduction to Linear Search Algorithm

Linear search is a simple and straightforward algorithm for finding an element from a list. It is also known as a sequential search because this algorithm search the target element in a sequential manner means one after onther.

A linear search algorithm is used to find a specific element from a list. It works by iterating through the list and comparing each element to the target element. If a match is found, the index of the element is returned. Otherwise, the search keeps going until it reaches the end of the list.

How Does the Linear Search Algorithm Work?

The following steps are followed to search for an element in the list:

Step 1: Start at the beginning of the list.
Step 2: Compare the target element (element that we're searching) with the current element in the list.
Step 3: If they're a match, that means we found the target element! Stop the search and return the current element's position.
Step 4: If they're not a match, move on to the next element in the list.
Step 5: Repeat steps 2-4 until we reach the end of the list.
Step 6: If we reach the end of the list and haven't found the target element, it means it's not there. Return -1 (or some other indicator) to signify the element's absence.

Implementation of Linear Search Algorithm in Java:

  
  public class LinearSearchExample {
    // performing linear search in this static method
    static void linearSearch(int list[], int target_element) {
      int count = 0;
      for (int i = 0; i < list.length; i++) {
        // compares each element of the array
        if (list[i] == target_element) {
          System.out.println("The element is found at position: " + (i + 1));
          count = count + 1;
        }
      }
  
      // If count is 0 that means target element not found.
      if (count == 0)
        System.out.println("The element is not found in the array");
    }
  
    // Driver code
    public static void main(String args[]) {
      int target_element;
      int list[] = { 25, 80, 75, 35, 44, 90, 62 };
  
      // target element is present in the array 
      target_element = 44;
      linearSearch(list, target_element);
      
      // target element is not present in the array
      target_element = 54;
      linearSearch(list, target_element);
    }
  }

Output

The element is found at position: 5
The element is not present in the array

Time and Space Complexity of Linear Search Algorithm:

Time Complexity: The worst-case time complexity of linear search is O(n), which means it takes, at most, n comparisons to find the target element. This happens when the target element is at the very end of the list. On average, it takes n/2 comparisons. In the best-case scenario, where the target element is the first element in the list, it takes only one comparison.
Space Complexity: The space complexity of linear search is O(1), as it doesn't require any additional space beyond the list itself.

Applications of Linear Search Algorithm:

Unsorted Arrays or Lists: If we need to find an element from the unsorted array or list linear search algorithm is the best choice.
Small Data Sets: Instead of binary search, linear search is more preferred when we are working with small data set.
Searching Linked Lists: To find the element in Linked List, each node is checked sequentially (one after another) until the target element is found this process of searching is called linear search.
Simple and easy Implementation: In comparison of Binary Search or Ternary Search, Linear Search understanding and implmentation very easy and simple.

Advantages of Linear Search Algorithm:

Simple and easy understanding and implementation.
No additional memory required.
Best case time complexity of O(1).
Linear search algorithm can be used with sorted or unsorted both types of array or list.
Linear algorithm is a best choice for small datasets.
Works on any data structure that allows sequential access.

Disadvantages of Linear Search Algorithm:

Worst case time complexity is O(N).
Not suitable for data structures with non-sequential access.
Not suitable for very large data.
Not suitable for frequent searches.

That's all, guys. I hope this article is helpful for you.

Happy Learning... 😀

Please share this article on social media to help others.

If you have any queries or suggestions regarding this article, please share with us.
feedback@javabytechie.com