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

Main Concepts :

- Linear Search
- Binary Search
- Hashing
- Linked lists

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

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

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

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