How to implement Linear Search in Java? Example Tutorial (original) (raw)

Hello guys, earlier, I have talked about how the binary search algorithm works and shared the code to implement the binary search in Java. In that article, someone asked me about is there any other search algorithm that exists? How can you search an element in the array if it's not sorted, and you cannot use the binary search algorithm? To answer his questions, I mentioned the Linear search algorithm, which is the predecessor of binary search. Generally, it is taught before the binary search algorithm because the binary search is faster than Linear search. However, never mind, you can still learn this useful algorithm to search for an item in the array or linked list.

Linear search or sequential search is a method for finding a particular value in a list that consists of checking every one of its elements, one at a time and in sequence until the desired one is found.

The Linear search algorithm is the most straightforward. For a list of n items, the best case is when the value is equal to the first element of the list, in which case only one comparison is needed. The worst case is when the value is not in the list (or occurs only once at the end of the list), in which case n comparisons are needed.

The worst-case performance scenario for a linear search is that it has to loop through the entire collection, either because the item is the last one, or because the item is not found.

In other words, if you have N items in your collection, the worst-case scenario to find a topic is N iterations. In Big O Notation it is O(N). The speed of search grows linearly with the number of items within your collection. Unlike the Binary Search algorithm, Linear searches don't require the collection to be sorted.

Btw, if you are not familiar with the essential data structure and algorithms like this one, it's better to first go through a suitable data structure and algorithm course like Data Structures and Algorithms: Deep Dive Using Java. This is a comprehensive resource to learn fundamental data structures and algorithms in Java programming languages. It's also very affordable, and you can buy it for just $10 on Udemy's monthly sale.

Java Program to implement Linear Search with Example

Here is our sample program to implement a sequential search algorithm in Java. It's self-explanatory, but if you have any doubt in understanding any part of the code then please shout and I would be happy to clear any doubt you have.

You can also read the Grokking Algorithms book, one of my favorite books to learn the fundamentals of Data Structure and Algorithms. It has a whole chapter on the liner and binary search and here is a diagram that neatly explains the difference between linear and binary search algorithms.

You can see how the linear search algorithm because slower and slower as the size of the array or number of elements increases.

import java.util.Arrays; import java.util.Scanner;

/**

• Java program to implement linear search algorithm in Java. It's also known as

• sequential search, because its sequentially search array for desired element.

• It's best case performance is O(1), when number is located at first index of

• array, in worst case it can take upto N array index access and N comparison.

• In Big O notation, time complexity of linear search is O(n), where n is

• number of elements in array.

• @author Javin */ public class LinearSearchDemo {

  public static void main(String args[]) {

    int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
  
    for (int number : primes) {
        int index = linearSearch(primes, number);
        if (index != -1) {
            System.out.printf("'%d' is found at index '%d' %n", number,
                     index);
        } else {
            System.out.printf("'%d' not found in array %n", number,
                 Arrays.toString(primes));
        }
    }

  }

  /**

  • Search a number in array using linear search algorithm. It's one of the
  • simplest algorithm in programming world, which just require iterating
  • over array and comparing each element with desired one. Once found you
  • break the loop and return index of element.
  • @param array
  • @param number
  • @return index of number in array, or -1 if not found */ public static int linearSearch(int[] array, int number) { for (int i = 0; i < array.length; i++) { if (array[i] == number) { return i; } } return -1; // Number not found in array }

}

Output: '2' is found at index '0' '3' is found at index '1' '5' is found at index '2' '7' is found at index '3' '11' is found at index '4' '41' is found at index '12' '43' is found at index '13' '47' is found at index '14'

That's all about how to implement a linear search algorithm in Java. It is one of the first search algorithms you should learn in your computer science class. Teachers and Professors explain binary search next, but you have already learned that. Never mind, we have a lot of sorting algorithms that you can explore after this, and the following article will help you.

If you are preparing for interviews and ramping up your Data structure and algorithms skills, you can also take a look at the following resources to take your preparation next level:

Other S earching and Sorting algorithm tutorials you may like

• How to implement the insertion sort algorithm in Java? (tutorial)
• How to apply the Quicksort algorithm in place in Java? (tutorial)
• How to implement the Bubble sort algorithm in Java? (tutorial)
• Difference between Comparison and Non-Comparison based sorting algorithm? (answer)
• How to apply Bucket Sort in Java? (tutorial)
• How to implement Quicksort algorithm without recursion? (tutorial)
• How to perform a Binary Search Algorithm in Java? (tutorial)
• How to find all pairs in an array whose sum is equal to k (solution)
• How to remove duplicates from an array in Java? (solution)
• How to find the most significant and smallest number in an array without sorting? (solution)
• How to find duplicates from an unsorted array in Java? (solution)
• How to find one missing number in a sorted array? (solution)
• How to find a missing value from an array containing 1 to 100? (solution)
• How to count the number of leaf nodes in a given binary tree in Java? (solution)
• Recursive In Order traversal Algorithm (solution)
• 50+ Data Structure and Algorithms Problems from Interviews (questions)
• My favorite free courses to learn data Structure in-depth (FreeCodeCamp)
• How to remove an element from an array in Java? (solution)
• How to check if an array contains a particular value? (solution)
• Iterative PreOrder traversal in a binary tree (solution)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• 100+ Data Structure Coding Problems from Interviews (questions)

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

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 courses to learn Data Structure and Algorithms on Udemy.