int function SequentialSearch (Array A, int Lb, int Ub, int Key); begin for i = Lb to Ub do if A(i) = Key then return i; return -1; end; |
This is a powerful method. Given an array of 1023 elements, we can narrow the search to 511 items in one comparison. Another comparison, and we're looking at only 255 elements. In fact, we can search the entire array in only 10 comparisons.
In addition to searching, we may wish to insert or delete entries. Unfortunately, an array is not a good arrangement for these operations. For example, to insert the number 18 in Figure 1-1, we would need to shift A[3]...A[6] down by one slot. Then we could copy number 18 into A[3]. A similar problem arises when deleting numbers. To improve the efficiency of insert and delete operations, linked lists may be used.
int function BinarySearch (Array A, int Lb, int Ub, int Key); begin do forever M = (Lb + Ub)/2; if (Key < A[M]) then Ub = M - 1; else if (Key > A[M]) then Lb = M + 1; else return M; if (Lb > Ub) then return -1; end; |
Insertion and deletion operations are very efficient using linked lists. You may be wondering how pointer P was set in the first place. Well, we had to do a sequential search to find the insertion point X. Although we improved our performance for insertion/deletion, it has been at the expense of search time.X->Next = P->Next; P->Next = X;
n | lg n | n lg n | n^{1.25} | n^{2} |
---|---|---|---|---|
1 | 0 | 0 | 1 | 1 |
16 | 4 | 64 | 32 | 256 |
256 | 8 | 2,048 | 1,024 | 65,536 |
4,096 | 12 | 49,152 | 32,768 | 16,777,216 |
65,536 | 16 | 1,048,565 | 1,048,476 | 4,294,967,296 |
1,048,476 | 20 | 20,969,520 | 33,554,432 | 1,099,301,922,576 |
16,775,616 | 24 | 402,614,784 | 1,073,613,825 | 281,421,292,179,456 |
Table 1-1 illustrates growth rates for various functions. A growth rate of O(lg n) occurs for algorithms similar to the binary search. The lg (logarithm, base 2) function increases by one when n is doubled. Recall that we can search twice as many items with one more comparison in the binary search. Thus the binary search is a O(lg n) algorithm.
If the values in Table 1-1 represented microseconds, then a O(lg n) algorithm may take 20 microseconds to process 1,048,476 items, a O(n^{1.25}) algorithm might take 33 seconds, and a O(n^{2}) algorithm might take up to 12 days! In the following chapters a timing estimate for each algorithm, using big-O notation, will be included. For a more formal derivation of these formulas you may wish to consult the references.
Linked lists improved the efficiency of insert and delete operations, but searches were sequential and time-consuming. Algorithms exist that do all three operations efficiently, and they will be the discussed in the section on dictionaries.