Algorithms in a Nutshell

Sequential Search | 107

Searching

Output

Returnstrue ift belongs toC, andfalse otherwise.

Context

Sometimes you need to locate an element in a collection. You may have to find

elements in the collection frequently, and the collection may or may not be

ordered. With no further knowledge about the information that might be in the

collection, SEQUENTIALSEARCHgets the job done in a brute-force manner. It is

the only search algorithm you can use if the collection is accessible only through

an iterator that returns the elements of the collection one at a time.

Forces

SEQUENTIALSEARCHmight be the most effective search method, depending

uponn, the number of elements in the collectionC, and the number of times you

will perform such a search. Ifnis relatively small or you won’t be performing the

search overCoften, the cost of sorting the elements or using a complex data

structure might outweigh the resulting benefits.

If the collection is unordered and stored as a linked list, then inserting an element

is a constant time operation (simply append to the end of the list or prepend to

the beginning). Frequent insertions into an array-based collection require dynamic

Figure 5-1. Sequential Search fact sheet

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