Occasionally programming tricks can be used to enhance efficiency. In this case paying attention to some details produces a trick that can pay off by saving processing time. The straightforward implementation of the linear search requires a test (loc ?/FONT> n) for the end of the array before checking the next element. This is true whether the implementation is a for loop or a while loop. However, it is possible to avoid performing this test.
Place the search key in element n + 1 of data. Then, in implementing the linear search, there is no need to test for the end of the array before checking the next element. Since the array is now considered to be (n + 1) elements in length, we are certain to find the search key before we "fall off the end." After the loop is exited, note the element in which key was found, and test to see if it was the (n + 1)th element, which means that the search was unsuccessful. Thus only one test (data[loc].key ! = key) must be performed. This saves n tests in unsuccessful searches, and i tests in successful searches, when the search key appears in element i of data. This simple modification of the basic linear search can easily produce significant time savings (20 to 50 percent). In general, whenever loops are modified to reduce the tests or processing they perform, execution time is saved each time through the loop. The more efficient linear search implementation appears as follows:
Another way to save time in a linear search is to order the records in the array. One way to do this is to store them in decreasing order of key value. The linear search can then be modified by terminating the search as soon as a record is reached whose key value is less than the search key. The desired record cannot be in the array past that point. Although this results in extra comparisons for successful searches, time is saved overall when unsuccessful searches occur frequently enough.
It is also possible, if the frequency with which records will be retrieved is known, to store the records in decreasing order of retrieval frequency. The most frequently retrieved record will then be at the top of the array. This approach significantly improves search efficiency when the desired record is likely to be near the top of the array. In fact, if the frequencies decrease rapidly enough, the average search time for the linear search will be a small constant.
#define MAX 100
typedef struct
{int key;
}record;
typedef record recordarray[MAX];
linearsearch(data,n,key,pfound,ploc)
/* Searches the n records stored in
the array data for the search key.
Found will be true only if a record
is present with key field equal to
the search key value and then loc
will contain its array index.
*/
recordarray data;
int n,key,*pfound,*ploc;
{*ploc = 1;
data[n + 1].key = key;
while (data[*ploc].key != key)
(*ploc)++;
*pfound = (*ploc < n + 1);
}