How to implement Linear Search in Java? Example tutorial

In the last article about searching and sorting, we have learned 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 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 definitely not suitable for a large array. It's practically useful only in case of the small array up to 10 to 15 numbers. In the worst case, you need to check all elements to confirm if target element exists in an array or not.

The time complexity of linear search algorithm is O(n) where n is the number of elements in the target array, which shows its slower than 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, I would suggest starting reading Grokking Algorithms by Aditya Bhargava, one of the interesting book on algorithms with lots of easy to understand diagrams, visuals, and real-world explanation. I am reading this book now and it's truly interesting.



Java Program to implement Linear Search

Here is our program to implement linear search in Java. It performs liner 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 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. The logic of linear search algorithm is encapsulated in the linearSearch(int[] input, int target) method, 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 target element in array. 

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

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

How to implement Linear Search in Java? Example tutorial


Anyway, here is our Java program to implement binary search algorithm using recursion:


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 array at index

That's all about how to implement 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 first case and 22 in second case. It's one of the simplest searching algorithm but very important to learn and understnad linked list data structure, which only support linear search algorithm.

Further Learning
Algorithms and Data Structures - Part 1 and 2
Java Fundamentals, Part 1 and 2
Cracking the Coding Interview - 189 Questions and Solutions
How to do quicksort algorithm in Java?
Write a program to implement bubble sort in Java?
How to implement insertion sort algorithm in Java?
How to sort an array in descending order in Java?

Thanks for reading this article. If you like then please share with your friends and colleagues. If you have any questions or feedback, please drop a note.

No comments:

Post a Comment