Linear Search

February 13, 2019 3 minutes

Linear Search is one of the most fundamental searching algorithm in computer science. The same is also known as Sequential Search becuase of the fact that this algorithm is mostly used on linear or sequential data structures like lists, arrays etc.

The idea behind linear-search algorithm is to compare each element present in the underlying data structure that we need to search, with the key element that we need to find. We break the searching process when either of the following two conditions is met :

  1. We have found the element.
  2. There are no more elements in the datastructure to be compared.

LinearSearch

Complexity : O(n)

As the linear-search algorithm does not consider the nature of the data present in the database and involves comparing every element, the complexity of this algorithm is directly proportional to the size or number of elements present in the datastructure.

Pseudo Code

  1. initialise
    • size = number of elements present in the lists
    • key = the element that we need to find
    • index = start of the list
  2. while index < size
    • check if element at position index == key
    • if yes, we have found a match, break the loop and return index
    • else, set index = index + 1; i.e move to next element

Java Implementation

// a method to perform linearSearch on array input
// to find the number denoted by key
// if the key is not present in the input array return -1
public int linearSearch(int[] input, int key) {

     //for all non-null inputs
     if (null != input) {
        int size = input.length;
        //iterate over the input array
        for (int index = 0; index < size; index++) {
            if (input[index] == key) {
               //key is found at location index, return the same
               return index;
            }
        }
     }

     //key not present in the input[], return -1
     return -1;
}

In addition to this classic approach mentioned above, we can also use features provided by java8 and later versions to use more of functional programming style coding. A few of the commonly used code snippets are :

//check if the key is present in the input array or not 
return Arrays.stream(input).filter(ithEntry -> key == ithEntry).findFirst().isPresent();

We can also use the stream to find the index, where the key present in the input (in addition to just returning a boolean as mentioned above). But this implementation requires the index to be of the type AtomicInteger as the lambda expressions allows only final variables in case those are not thread safe.

AtomicInteger index = new AtomicInteger(-1);
IntStream.range(0, input.length).forEach(i -> {
	if (input[i] == key) {
		index.set(i);
	}
});

//return this will return the actual index set (if present) or else the default -1 
return index.get();

A working implementation of this can be found here


comments powered by Disqus