Linear Search

How it works

The simplest way to search for an item is to simply start at the beginning of the list, and look at each item in turn until either:

• You find the item that you are looking for, or
• You reach the end of the list without finding what you are after, in which case the item does not exist in the list

Pseudocode

sub LinearSearch(data, target)
  foundAt = -1
  for i = 0 to len(data)
    if data[i] == target then
      foundAt = i
      break
    end if
  end for
  return foundAt
end sub

Time efficiency

Assuming the worst case (that is, the item being searched for is the last item in the list or it doesn’t exist), then the complexity is O(n).

As the number of items in the list doubles, the number of comparisons that potentially need to be completed in order to find an item also doubles.

Advantages

This algorithm can search unsorted data – as it looks at each item in a list, one by one until it finds what it is looking for, the data being searched does not need to be in any specific order.

It is also a very simple algorithm to implement – look at the pseudocode above.

Disadvantages

There are more efficient search algorithms (for example binary search) which work far better with large data sets, although in contrast to a linear search, these require data to be ordered.