Thousands of software applications, including databases or commercial search engines such as Google, depend on the ability to quickly search through huge amounts of data to find a particular item.

Two of the most common search routines are the  Linear search and the Binary Search

Look through this video and PowerPoint for some general information.


Linear Search

This video illustrates a linear search. Each item is looked at in turn until a match is found. This could mean that the match is found immediately or that  every piece of data in the array has to be compared.

Here is the pseudocode for a linear sort: 

Binary Search

This video illustrates the Binary Search. The list MUST be sorted to carry out a binary search. If the list is sorted, (i.e. in numerical or alphabetical order), you can use a much more efficient algorithm. It works by repeatedly dividing in half the portion of the data list that could contain the required data item. This is continued until there is only one item in the list you are examining.

Here is the pseudocode for a binary search.

Comparing linear and binary search algorithms

  • A linear search has an algorithm that is easier to understand, whereas the binary search algorithm is more complex.
  • The binary search will be much quicker than a linear search – particularly where the volume of data being searched is large.
  • The linear search algorithm is fine for just a few items, but for a very large number of items as it is inefficient. If you had to search a database of 10 million car registrations to find who owns a certain car, it would take a very long time.
  • The binary search algorithm is extremely efficient. Each time an item is examined, if it is not the right one, half the list is discarded. In a list of 10 million items, only 24 items would need to be examined.
  • In general, if there are fewer than 2n items (but at least 2n-1), the maximum number of items that needs to be examined is n.
  • A key benefit of the linear search is that it can be done on an unsorted list - the items do not have to be in sequence. If items are frequently added or deleted from the list, this saves the extra work needed to keep the list in sequence in order to do a binary search.

Further Revision