Java Reference
In-Depth Information
9
Searching
Organizing and retrieving information is at the heart of most computer applica-
tions, and searching is surely the most frequently performed of all computing tasks.
Search can be viewed abstractly as a process to determine if an element with a par-
ticular value is a member of a particular set. The more common view of searching
is an attempt to find the record within a collection of records that has a particular
key value, or those records in a collection whose key values meet some criterion
such as falling within a range of values.
We can define searching formally as follows. Suppose that we have a collection
L of n records of the form
(k 1 ;I 1 ); (k 2 ;I 2 );:::; (k n ;I n )
where I j is information associated with key k j from record j for 1 j n. Given
a particular key value K, the search problem is to locate a record (k j ;I j ) in L
such that k j = K (if one exists). Searching is a systematic method for locating the
record (or records) with key value k j = K.
A successful search is one in which a record with key k j = K is found. An
unsuccessful search is one in which no record with k j = K is found (and no such
record exists).
An exact-match query is a search for the record whose key value matches a
specified key value. A range query is a search for all records whose key value falls
within a specified range of key values.
We can categorize search algorithms into three general approaches:
1. Sequential and list methods.
2. Direct access by key value (hashing).
3. Tree indexing methods.
This and the following chapter treat these three approaches in turn. Any of
these approaches are potentially suitable for implementing the Dictionary ADT
301
 
Search WWH ::




Custom Search