Algorithms in a Nutshell

Sequential Search | 109

Searching

A C implementation of SEQUENTIALSORTis shown in Example 5-3, where the

collection is stored in an array (ar) and the comparison functioncmpreturns 0 if

two elements match.

Consequences

For small collections of unordered elements, SEQUENTIALSEARCHis easy to

implement and reasonably efficient. The worst case is when you search for an

item not in the collection, since you must inspect every element in the collection.

If the predominant result of a search isfalse, you may want to consider a

different search algorithm, even when the collection is relatively small.

Sometimes, you may have an indexed collection that has “holes” in it. That is,

there are index values in the collection where no element is stored.*In this case,

you must add code to your implementation to check each index value, in order to

ensure that there is an element in it. We would modify the code in Example 5-1

with an additional check, as shown in Example 5-4.

}

return false;

}

/** Apply the brute-force Sequential Search algorithm to search the

* iterable collection (of type T) for the given target item. */

public boolean sequentialSearch (Iterable<T> collection, T t) {

Iterator<T> iter = collection.iterator( );

while (iter.hasNext( )) {

if (iter.next( ).equals(t)) {

return true;

}

}

return false;

}

}

Example 5-3. C implementation of Sequential Sort

int search (void *t, int(*cmp)(const void *,const void *)) {

int i;

for (i = 0; i < n; i++) {

if (!cmp(ar[i], t)) {

return 1;

}

}

return 0;

}

* To be more precise, a collectionAmay have itsithelementA[i] equal to the special valuenil.It

is quite rare for collections accessed using iterators to emitnil values.

Example 5-2. Sequential Search in Java (continued)

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