How to implement Linear Search Algorithm in Java? Example tutorial

In the last article about searching and sorting, you have learned the binary search algorithm and today I'll teach you another fundamental searching algorithm called Linear search. Linear search is nothing but iterating over the array and comparing each element with the target element to see if they are equal since we search the array sequential from start to end, this is also known as sequential search or linear search. It is very slow as compared to binary search because you have to compare each element with every other element and is definitely not suitable for a large array. It's practically useful only in the case of a small array of up to 10 to 15 numbers. In the worst case, you need to check all elements to confirm if the target element exists in an array or not.

The time complexity of the linear search algorithm is O(n) where n is the number of elements in the target array, which shows it's slower than the binary search algorithm, whose time complexity was O(logN) because it was dividing the array into two part in every iteration.

Actually, the learning order is to first learn linear search and then the binary search but and we all learned that way but I found that when you first code binary search, then linear search becomes extremely easy and it also easier to reason about its time and space complexity and performance, hence I presented this algorithm after binary search.

Btw, if you enjoy learning algorithms and want to see the application of algorithms in the real world but struggle with calculating time and space complexity, I would suggest going through these comprehensive courses on Data Structure and algorithms. This will not only teach you essential algorithms but fundamentals data structures like the array, linked list, hash table, binary tree, etc.

Java Program to implement Linear Search

Here is our program to implement a linear search in Java. It performs a linear search in a given array. It first asks users to enter the size of the array and then each element. Once the array is filled, it asks the user for the target element. It then performs linear search and returns the index of the target element in the array, if it exists.

If you want, you can also modify the algorithm to work on a pre-populated array, instead of asking the user to provide it. The logic of the linear search algorithm is encapsulated in the linearSearch(int[] input, int target) method, which you can use as you wish. You need to just pass the integer array and target number and it will return you the index of the target element in the array. 

If you like to learn more about searching and sorting algorithm, I suggest you check out then Algorithms and Data Structures - Part 1 and 2, two great courses from Pluralsight. They are not completely free but you need to sign up for a trial, which gives you 10 days of free access to all courses in Pluralsight.

In practice, the algorithm work is just like given in this diagram:

And, if you like books then you must check out the Grokking Algorithms by Aditya Bhargava, one of the most interesting books on algorithms with lots of easy-to-understand diagrams, visuals, and real-world explanations. I am reading this book now and it's truly interesting.

Linear Search Algorithm in Java - Example

Anyway, here is our Java program to implement a linear search algorithm:

import java.util.Scanner;

/*
 * Java Program to implement binary search algorithm
 * using recursion
 */

public class LinearSearchAlgorithm {

  public static void main(String[] args) {

    Scanner commandReader = new Scanner(System.in);
    System.out
        .println("Welcome to Java Program to perform linear 
                search on int array");
    System.out.println("Enter length of array : ");
    int length = commandReader.nextInt();
    int[] input = new int[length];

    System.out.printf("Enter %d numbers %n", length);
    for (int i = 0; i < length; i++) {
      input[i] = commandReader.nextInt();
    }

    System.out.println("Please enter target number");
    int target = commandReader.nextInt();

    int index = linearSearch(input, target);

    if (index == -1) {
      System.out.printf("Sorry, %d is not found in array %n", target);
    } else {
      System.out.printf("%d is found in array at index %d %n", target, index);
    }

    commandReader.close();

  }

  /**
   * Java method to liner search an element in array
   * 
   * @param input
   * @param target
   * @return index of target element or -1 if not found
   */
  public static int linearSearch(int[] input, int target) {

    for (int i = 0; i < input.length; i++) {
      if (input[i] == target) {
        return i;
      }
    }
    return -1;
  }

}

Output
Welcome to Java Program to perform linear search on int array
Enter length of array : 
7
Enter 7 numbers 
1
2
2
3
4
5
6
Please enter target number
4
4 is found in array at index 4 
Welcome to Java Program to perform linear search on int array
Enter length of array : 
3
Enter 3 numbers 
22
33
44
Please enter target number
22 

22 is found in the array at index 0 

You can see that our program has successfully able to find the index of the target element using Linear search or Sequential Search Algorithm in Java. If you are more curious you can also run this program with a large array, something which you can create programmatically.

For example int[] numbers = new int[Integer.MAX_VALUE] will create a really large array and if you just put 1 in the last index and then search for it, your program will take a long time to respond because it has to go through 2^32-1 elements to reach the last element.


That's all about how to implement a linear search in Java. You can see that our algorithm is working correctly and it found out the right index for target value, 4 in the first case, and 22 in the second case. It's one of the simplest searching algorithms but very important to learn and understand the linked list data structure, which only supports the linear search algorithm.


Other Data Structure and Algorithms Articles You May Like

• How binary search algorithm works? (solution)
• How to reverse a singly linked list in Java? (solution)
• How to implement a binary search in Java without recursion? (solution)
• How to find the middle element of the linked list using a single pass? (solution)
• How to find the 3rd element from the end of a linked list in Java? (solution)
• Top 15 Data Structure and Algorithm Interview Questions (see here)
• Top 20 String coding interview questions (see here)
• 40 Data Structure Coding Interview Questions for Programmers (questions)
• Top 30 Array Coding Interview Questions with Answers (see here)
• Top 30 linked list coding interview questions (see here)
• Top 50 Java Programs from Coding Interviews (see here)
• 5 Free Data Structure and Algorithms Courses for Programmers (courses)
• 10 Algorithms Books Every Programmer Should Read (books)
• 50+ Data Structure and Algorithms Problems from Interviews (questions)
• 10 Free Data Structure and Algorithm Courses for Programmers (free courses)
• 100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this article. If you like then please share it with your friends and colleagues. If you have any questions or feedback, please drop a note. If you have any questions or doubt then please let us know and I'll try to find an answer for you. As always suggestions, comments, innovative and better answers are most welcome. 

Btw, what is your favorite search algorithm? Linear Search, Binary Search, BFS, or DFS?

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check these free Data Structure and Algorithms courses from Coursera and Udemy.