Lesson 22 - Learning Goals


22.1 Learn why searching is useful


22.2 Learn several different searching Techniques

22.3 Learn how to compare different searching algorithms


Searching Routines

Main Concepts :

  1. Linear Search
  2. Binary Search
  3. Hashing
  4. Linked lists

Linear Search

This is the simplest searching technique, and corresponds to running your eye down a printed list from top to bottom.

For examples :

See P101.F90

See P102.F90

See P103.F90


Binary Search

While the linear search is easy to program, it is not computationally efficient, because, on average, half the list of elements have to be inspected. Given a set of records, such as a class list or a phone book, they will most likely be sorted in order. The next search technique we will look at corresponds more closely to how people would in fact look up a name in a phone book. If you were looking for SMITH, JOHN you might open the phone book near the middle, maybe in the P's. In this case, you know that SMITH cannot be in the first section before P, so you ignore that section and then break the second section open, maybe in the T's. At this point, you know that the name you are seeking is not in the last part and you have narrowed the section that contains SMITH to a small portion bounded by the P's and the T's. This took only two comparisons and the process could be continued until the desired page is found.

The binary search is a systematic algorithm that implements the above idea by dividing the list in half and then testing the element at the center of the list to decide which half to ignore and which half should be further subdivided.

To use Binary Search :

The data MUST be sorted in key order.

The data MUST be randomly accessible.

See example program P104.F90


Hashing

The idea here is to define a set of locations for the stored data, which is somewhat larger than actually needed. As the data is read, it is spread in a quasi-random manner into the locations, but in such a way that the computer can find a given record when required.

See example program P105.F90


Linked Lists

The idea of a linked list is that each record, which must be randomly accessible, has an extra field, which points to the next record in sequence. This extra field, in our case, will just be an INTEGER number stored in the LINK array, and which contains the index number of the next record. By convention, the end of the list is marked with a zero in the LINK field.

See example program P106.F90


Go back to lecture menu

Go back to main page


Copyright © 1996 McGill University. All rights reserved.