(^108) | Chapter 5: Searching
array management, which is either provided by the underlying programming
language or requires specific attention by the programmer. In both cases, the
expected time to find an element is O(n); thus, removing an element takes at least
O(n).
SEQUENTIALSEARCHplaces the fewest restrictions on the type of elements you
can search. The only requirement is that there must be a match function to deter-
mine whether the target element being searched for matches an element in the
collection; often this functionality is delegated to the elements themselves. No
additional ordering is required.
Solution
Often the implementation of SEQUENTIALSEARCHis trivial. If the collection is
stored as an array, you need only start at the first element of the array and
compare it to the target,t. If it matches, returntrue. If not, go to the next element
and continue until you find the element you’re looking for. If you reach the end of
the array without success, returnfalse.
The Ruby code in Example 5-1 searches sequentially through an array of
elements.
The code is disarmingly simple. The function takes in a collection and the target
itemtbeing sought. The collection can be an array or any other collection that
supports theeachmethod in Ruby. Elements involved in the search must support
the == operator; otherwise, you need to use one of the other types of equality
operators supported in Ruby. This same example written in Java is shown in
Example 5-2. TheSequentialSearchgeneric class has a type parameter,T, that
specifies the elements in the collection;Tmust provide a validequals(Object o)
method.
Example 5-1. Sequential Search in Ruby
def sequentialSearch(collection, t)
collection.each {
|i| if i == t then return true; end
}
return false
end
Example 5-2. Sequential Search in Java
package algs.model.search;
import java.util.Iterator;
public class SequentialSearch
/** Apply the brute-force Sequential Search algorithm to search the
- indexed collection (of type T) for the given target item. */
public boolean sequentialSearch (T[] collection, T t) {
for (T item : collection) {
if (item.equals(t)) {
return true;
}
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