Further algorithms - EdexcelLinear search

A linear search is the simplest method of searching a data set.

Starting at the beginning of the data set, each item of data is examined until a match is made. Once the item is found, the search ends. If there is no match, the algorithm must deal with this.

A written description algorithm for a linear search might be:

1. Find out the length of the data set.
2. Set counter to 0.
3. Examine value held in the list at the counter position.
4. Check to see if the value at that position matches the value searched for.
5. If it matches, the value is found. Send a message and end the search.
6. If not, increment the counter by 1 and go back to step 3 until there are no more items to search.
7. If all the items have been checked and no match is found, send a message.

Consider this list of unordered numbers:

Suppose we were to search for the value 2 in this list. The search would start at position 0 and check the value held there, in this case 3. 3 does not match 2, so we move on to the next position.

The value at position 1 is 5. 5 does not match 2, so we move on to the next position.

The value at position 2 is 2 - a match. The search ends.

A linear search in pseudo-code might look like this:

SET find TO 2 SET found TO False SET length TO LENGTH(list) SET counter TO 0 WHILE found = False AND counter < length DO IF list[counter] = find THEN SET found TO True SEND 'Found at position' & counter TO DISPLAY ELSE SET counter TO counter + 1 END IF END WHILE IF found = False THEN SEND 'Item not found' TO DISPLAY END IF

Although simple, a linear search can be quite inefficient. Suppose the data set contained 100 items of data, and the item searched for happens to be the last item in the set. All of the previous 99 items would have to be searched through first.

However, linear searches have the advantage that they will work on any data set, whether it is ordered or unordered.