Please navigate to the bottom of the page for Table of Contents

Tuesday, May 17, 2011

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.   


7 comments:

  1. This does not work, aren't you skipping the last element in the array ??

    ReplyDelete
    Replies
    1. He's not skipping the last element. An array starts at 0, not 1. He has given the value of 0 to i (int i=0).

      Delete
  2. This works : for (int i = 0; i <= input.Length - 1; i++)
    This works : for (int i = 0; i < input.Length - 0; i++)
    This works : for (int i = 0; i < input.Length; i++)

    THIS FAILS: for (int i = 0; i < input.Length - 1; i++)

    ReplyDelete
    Replies
    1. I am not the same anonymous :) why the confusion? i < input.Length is correct. original code is definitely wrong. say your array length is 10, 0 to 9 is 10 iterations.

      Delete
  3. Hi,


    Amaze! I have been looking bing for hours because of this and i also in the end think it is in
    this article! Maybe I recommend you something helps me all the time?

    This may well belong in the New to Java section but I keep getting logged out every time I enter that forum.

    I am creating code to issue tickets to passengers on 4 different bus routes, I am going to contain them in an array.
    Although, I have hit a wall in writing this code and I am stumped. I will post the 3 classes I have so far and the error I am getting.

    Also I would welcome any sort of guidance or recommendations.

    Awesome! Thanks for putting this all in one place. Very useful!


    Thank you,
    Morgan

    ReplyDelete
  4. Nice written!! I have been a big fan of your blogs. thanks
    Bay Area web design firms

    ReplyDelete
  5. Linear search, though straightforward, is a foundational algorithm in computer science. It sequentially examines each element in a dataset, making it suitable for small lists. The Security Wordpess While not the most efficient for large datasets.

    ReplyDelete