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

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