Searching algorithms–Linear search

Linear search, also sometimes referred as brute-force search or sequential search is one of the simplest search algorithms. It starts with checking if the first element of a list matches the target and continues on for each element of the list till a match is found or the end of the list is reached. For linear search, a data structure like an array or linked list is generally in play. Collections that are only accessible via an iterator are also good candidates for linear search.

So, what is the complexity of a linear search algorithm? Well, the best case is of course O(1). The worst case when the element is always at the last position is O(n). The average case is also O(n). The code for implementing a linear search is simple. Let's first see the code before we discuss more about this algorithm.

public static bool Search(int[] input, int target)
{
    for (int i = 0; i < input.Length - 1; i++)
    {
        if (input[i] == target)
            return true;
    }
    return false;
}

Why use sequential search?

So, given that the worst case performance characteristics of linear search, why would you want to use it? What are some of the scenarios where it is ok or even necessary to use this brute force algorithm?

• If your collection size is relatively small and you would be performing this search relatively a few times, then this might an option.
  
• Another case is when you need to have constant insertion performance (like using a linked list) and the search frequency is less.
  
• In addition, linear search places very few restrictions on the complex data types. All that is needed is a match function of sorts.

 

Linear Search Optimizations

If the elements you would be searching in a list are NOT uniformly distributed, then you could do certain optimizations that can help you improve the efficiency of your search algorithms. For such improvements to be effective, you do need to know the characteristics of the data being searched, the frequency and also the fact that the underlying collection needs to be modifiable.

• Most Recently Used pattern: If the likelihood of the current element being searched again is high, then move if from it's current location (say  position i) to the front of the collection (say position 0). This does require moving elements from A[0, i-1] to A[1, i] to accommodate the new element at A[0].
  
• The disadvantage of the above pattern is that it requires a lot of movement. One quick strategy is to move an element up on success by simply swapping the target element from position x with the first element at position 0. This eventually results in a similar pattern as the frequently searched elements bubble up to the top of the list.
  
• On the other end of the spectrum, if an element is unlikely to be search again, then moving it to the end on find improves the chances of the other elements being searched.

 

Hopefully, this will give you some good ideas and discussion points when you explore the linear search concept. We will be exploring binary search algorithm in the next post.