Back

A serial search algorithm

Searching for data
We know that sorting data means puting some data into some kind of order. We have seen examples of insertion and bubble sort algorithms and written some Python programs to see how they work. Searching for data means looking for a particular piece of data in a set of data. Just as there are algorithms for sorting data, there are also algorithms for searching for data.

Special cases
Whatever method is used for searching, you should always be aware that there are special cases common to all methods.

1. You may be searching for a piece of data that isn't actually in the set of data you are searching through.
2. You may be searching for a piece of data in an empty data structure, such as a list with no elements.
3. you may be searching for a piece of data that appears more than once.

A serial search
A serial search involves starting at the beginning of a file and checking each record in turn. You would need to check if the first record is the one you are looking for. If it is, then you can stop searching and report that you have found the record. If it isn’t the one you are looking for then you go on to the next record. You repeat this process until either you find the record you want or you come to the end of the file. If you do come to the end of the file without finding the record you want then you simply report that the record you are looking for isn’t in the file and stop searching! It doesn't actually matter if the records are in a particular order or not when you search through them when you do a serial search.

We are going to assume that a piece of data can appear only once for the moment. A typical algorithm for a serial search through a list called myList of size n to find the first instance of a piece of data is as follows:

Set a variable called index = 0    # this will be our counter, to work through a list
Set a Boolean flag called found = False    # this will indicate if we have found the item or not
Set a variable called hunted to be the data we are searching for.

while (index < n) and (found == false):
     if myList[index] == hunted
        found = true
     else
         index = index + 1

if found == true
     print("Item found at position", index)
else
     print("Item not found.")

Back