Table Search

Table Search

A search through an array is sometimes also called a table search, particularly if the keys are themselves structured objects, such as arrays of numbers or characters. The latter is a frequently encountered case; the character arrays are called strings or words. Let us define a type String as String = ARRAY M OF CHAR and let order on strings x and y be defined as follows:

In order to establish a match, we evidently must find all characters of the comparands to be equal. Such a comparison of structured operands therefore turns out to be a search for an unequal pair of comparands, i.e. a search for inequality. If no unequal pair exists, equality is established. Assuming that the length of the words be quite small, say less than 30, we shall use a linear search in the following solution. In most practical applications, one wishes to consider strings as having a variable length. This is accomplished by associating a length indication with each individual string value. Using the type declared above, this length must not exceed the maximum length M. This scheme allows for sufficient flexibility for many cases, yet avoids the complexities of dynamic storage allocation. Two representations of string lengths are most commonly used:

1. The length is implicitly specified by appending a terminating character which does not otherwise occur. Usually, the non-printing value 0X is used for this purpose. (It is important for the subsequent applications that it be the least character in the character set).

2. The length is explicitly stored as the first element of the array, i.e. the string s has the form s = s0, s1, s2, ... , sN-1 where s1 ... sN-1 are the actual characters of the string and s0 = CHR(N). This solution has the advantage that the length is directly available, and the disadvantage that the maximum length is limited to the size of the character set, that is, to 256 in the case of the ASCII set.

For the subsequent search algorithm, we shall adhere to the first scheme. A string comparison then takes the form
i := 0;
WHILE (x[i] = y[i]) & (x[i] # 0X) DO i := i+1 END
The terminating character now functions as a sentinel, the loop invariant is
Aj: 0
≤
j < i : xj = yj
≠
0X,
and the resulting condition is therefore
((xi = yi) OR (xi = 0X)) & (Aj: 0 < j < i : xj = yj
≠
0X)
It establishes a match between x and y, provided that xi = yi, and it establishes x < y, if xi < yi. We are now prepared to return to the task of table searching. It calls for a nested search, namely a search through the entries of the table, and for each entry a sequence of comparisons between components.