Algorithms in a Nutshell

Sequential Search | 111

Searching

In the best case, the first element in the collection is the desired target item, which

performs in O(1) constant time. The worst case for SEQUENTIALSEARCHoccurs

when you always search for an item not in the collection. In this case, you must

examine all elements in the collection, resulting in O(n) performance. In the average

case (as covered in Chapter 2 and shown in the table), the performance is O(n).

Variations

When the target element being sought is not uniformly distributed, there are vari-

ations that have been shown at times to improve upon SEQUENTIALSEARCH

without imposing an excessive burden on the programmer. Intuitively we want

the elements that reside near the front of the collection to be those that are most

likely to be sought. If you know something about the target items being sought

(especially the order in which you are looking for them), then perhaps the

following strategies can improve the performance of SEQUENTIALSEARCH. These

strategies are useful only for indexed collections that can be modified as the

search progresses:

Move to front on success

This strategy is suitable if there is an increased likelihood that an itemtbeing

searched for will be searched again. Whentis found at locationi, move the

elements fromA[0,i–1] toA[1,i], and movetintoA[0]. This intuition is the

basis for Most-Recently-Used (MRU) paging algorithms.

Move up on success

This strategy is suitable if there is an increased likelihood that an itemtbeing

searched for will be searched again; additionally, there is a desire to avoid the

cost of moving lots of elements. Whentis found at locationi, swap element

A[i–1] withA[i] (except wheniis already at the front of the collection). Intu-

itively, as items are found more frequently, they eventually “bubble” their way

to the head of the collection with very little overhead (just a single array swap).

Move to end on success

If an individual element is unlikely to be searched for multiple times, then

moving it to the end when it is found will improve the performance of future

searches. MoveA[i+1,n) toA[i,n–1), and move the found item intoA[n–1].

These variations all perform differently, based upon the probabilities of the

individual search terms. Choosing one of these depends on a significant under-

standing of your data collections and the items being sought. Analyzingsuch

algorithms is notoriously difficult, and requires mathematical techniques more

advanced than those presented in this book.

16,384 0.0324 0.0486 0.0524 0.0629

32,768 0.0624 0.0958 0.1141 0.1263

65,536 0.1304 0.2065 0.226 0.226

131,072 0.2627 0.3625 0.3779 0.4387

Table 5-1. Sequential Search performance (in seconds) (continued)

n p=1.0 p=0.5 p=0.25 p=0.0

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use