42 SEARCHING AND SELECTION ALGORITHMS
STUDY SUGGESTIONS
As you are working through the chapter, you should rework the examples to
be sure you understand them. For example, you should create a list of 5 to 8
elements and then use it to trace the sequential search and selection algorithms.
You should do the same thing with an ordered list of 7 and 15 elements and
binary search. Additionally, you should try to answer any questions before
reading on. A hint or the answer is in the sentences following the question.he act of searching for a piece of information in a list is one of the
fundamental algorithms in computer science. In discussing searching,
we assume that there is a list that contains records of information,
which in practice is stored using an array in a program. The records, or items,
are assumed to be in adjacent locations in the list, with no gaps or blank
records in the middle. The list locations will be indexed from 1 to N, which
represents the number of records in the list. Each record can be separated into
fields, but we will only be interested in one of these fields, which we will call
the key. Lists will be either unsorted or sorted based on their key value.
Records are in a random order in an unsorted list and are in order by increas-
ing key value in a sorted list.
When a list is unsorted, we only have one search option and that is to
sequentially look through the list for the item we want. This is the simplest of
the searching algorithms. We will see that this algorithm is not very efficient
but will successfully search in any list.
When a list of elements is sorted, the options for searching are expanded to
include binary search. Binary search takes advantage of the ordered nature of
the list to eliminate more than one element of the list with each comparison.
This results in a more efficient search.
A problem related to searching for a particular value is the selection prob-
lem, where we are interested in finding the element that meets some criterion.
It might be that we are looking for the fifth largest value, seventh smallest
value, or the median value in the list. We will look at two techniques that can
be used to solve this problem.T