A linear search is so named because it proceeds in sequence, linearly through an array. Suppose data in Figure 8.1 is an array of integers.* The task is to determine whether the number stored in the variable key is in the array, and if so, what its index is.
* To simplify the explanation in this chapter, the 0th array position will be ignored, and data stored in arrays will start in position 1 unless otherwise noted.
One obvious method would be to traverse the data array, checking each element of data to see if it contains the same value as key. If an element currently being processed did contain the same value as key, its index would simply be returned, and the search would be complete. Arriving at the end of data without having found the key value would mean that no element with that value is stored in the array. This procedure is easily implemented using a loop structure (as in the following function). The worst-case time required for its execution will be of the order n, written O(n), where n is the length of the data array. In particular, if the value being sought is in element i of the array, it will take O(i) time to find it. The linear search is implemented as follows:
A special but common case is when the search is always for a key known to be stored in the array, and each key stored is distinct and equally likely to be the search key. This is like standing in front of a locked door with a bunch of keys. You need to find the key that opens the door from among n keys in arbitrary order on your key-ring. The average time for such a search would be O(n/2). That is, on the average, you would look at half the keys, or half the elements of the array, before finding the right one.
Thus the procedure called linear search is so named, not only because it proceeds linearly through an array, but also because its processing time increases linearly with n; when n is doubled, the time required to complete the search is doubled.
#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;
while ((*ploc <= n) && (data[*ploc].key != key))
(*ploc)++;
*pfound = (*ploc < n + 1);
}