Linear Search Implementation in Java

• Linear or Sequential Search
  • Java Program for Linear Search
  • Pros and Cons of Linear Search
  • Analysis of Linear Search
• References

Linear or Sequential Search

Linear search algorithm traverse through the given list sequentially and checks every elements of the list, one at a time and in sequence, until the desired element is found or the list ends. Linear search also known as sequential search, is the simplest of all searching algorithms. It is a brute-force approach for locating a given element in a list. It finds the element by starting at the first element of the list and examining each subsequent element until the matching element is found or the list exhausts.

Linear search is proved very useful in the context when you need to search an element in a list and the list is not ordered. In that situation sequential search gets the job done by examining list elements sequentially.

Linear search might be the most effective search method, depending upon n, the number of elements in the list, and the number of times you will perform such a search. If n is relatively small or you won't be performing the search over the list often, the cost of sorting the elements or using a complex data structure might outweigh the resulting benefits.

Linear search places the fewest restrictions on the type of elements you can search. The only requirement is that there must be a match function to determine whether the target element being searched for matches an element in the list. No additional ordering is required.

Java Program for Linear Search

The implementation of sequential or linear search is trivial. If the list is stored as an array, you need only start at the first element of the array and compare it to the target. If it matches, return true. If not, go to the next element and continue until you find the element you are looking for. If you reach at the end of the list without success, return false. The following program develops a class SequentialSearch containing two overloaded generic methods named sequentialSearch. For those who are beginners, generics in Java allow to write code that can be reused for objects of many different types.

/* Java program demonstrating sequential or linear search.*/
import java.util.Iterator;
import java.util.*;
class SequentialSearch 
{
  /* Apply sequential search to search the indexed list (of type T) for the given item. */
  public static <T> boolean sequentialSearch (T[] list, T searchKey) 
  {
    for (T item : list) 
    {
      if (item.equals(searchKey)) 
      {
        return true;
      }
    }
    return false;
  }
 
  /* Apply sequential search to iterable collection (of type T) for the given item. */
  public static <T> boolean sequentialSearch (Iterable<T> collection, T searchKey) 
  {
    Iterator<T> iter = collection.iterator( );
    while (iter.hasNext()) 
    {
      if (iter.next( ).equals(searchKey)) 
      {
        return true;
      }
    }
    return false;
  }
}
 
public class SequentialSearchDemo
{
  public static void main (String[] args)
  {
    Integer arr[] = {10, 9, 3, 8, 5, 6, 7, 4, 2, 1};
    Integer searchKey = new Integer("5");
 
    /* Uses first definition of sequentialSearch and search through the indexed list */ 
    System.out.println("Search key " + searchKey + " is found? " + SequentialSearch.sequentialSearch (arr, searchKey));
 
    ArrayList<Integer> arrList = new ArrayList<Integer>(Arrays.asList(arr));
    /* Uses second definition of sequentialSearch and search through the iterable collection */ 
    System.out.println("Search key " + searchKey + " is found? " + SequentialSearch.sequentialSearch (arrList, searchKey));
  }
}
 
OUTPUT
======
Search key 5 is found? true
Search key 5 is found? true

Both methods of SequentialSearch are static, therefore it is not needed to create an object of class SequentialSearch in order to call sequentialSearch methods. Both methods operate on type parameter T that specifies the elements in the collection; T must provide a valid equals(Object o) method.

Pros and Cons of Linear Search

For small lists of unordered elements, sequential search is easy to implement and reasonably efficient. The worst case is when we search for an item not in the list, since we must inspect every element in the list. If the list is large enough and does record frequent additions and deletions then it is better not to apply sequential search on the list. Rather, sort the list once and use binary search. We are discussing binary search in next section.

Analysis of Linear Search

In the best case, the first element in the collection is the desired target item, which performs in O(1) constant time. The worst case for sequential search occurs when we always search for an item that either found at last position or not present in the collection. In this case, we must examine all elements in the collection, resulting in O(n) performance.

Last Word

In this tutorial we discussed linear search. We implemented linear/sequential search algorithm in Java. Hope you have enjoyed reading this tutorial. Please do write us if you have any suggestion/comment or come across any error on this page. Thanks for reading!

References