Since base and arr point to data objects of type STR, we can say that base[0] = arr[0], base[1] = arr[1] , and so on. Now suppose the user enters `B' as the first character in the search string. A simple linear search would tell us that variables base[1] and base[2] provide partial matches. We'd like to arrange things so that when the user chooses the next character in the search string, the same linear search routine will be able to tell us the new candidates for the search. We can do this if we make base point to the second character in arr[1] and restrict the maximum index for base to 1, as shown in Figure 2.
Figure 2: Pointer configuration after entering code>.
If the user enters `L' as the search character, we can apply linear search to base[0] through base[1] and determine that a match results only for index 1. This terminates the search in this example. In effect, we're using base as a movable template for our string search. Each time a search character is entered, the range of indices that yield a match is computed and the value of base is shifted accordingly.
Three points bear mentioning. One is that the algorithm depends upon representing the string to be searched as a two-dimensional array of characters. We're assuming that characters in the strings are stored in contiguous memory locations.
Second, base points to a data object of size six. This ensures that base[0], base[1], and so on are offset from one another by six bytes, so the relative offsets that apply to elements of the array arr are preserved.
Finally, the strings referenced by the base pointers in Figures 1 and 2 are in alphabetical order. This is no accident. It's a consequence of the fact that entries in arr are in sorted order and we're limiting the offsets that are added to base. If our search algorithm had referenced base[2] in Figure 2 (a pointer to the string "ANE"), then base[0] through base[2] would not be in sorted order. Part of the housekeeping the incremental search algorithm must perform involves knowing what range of offsets we can safely add to base to preserve sorted order.
