Page 215 - Discrete Mathematics and Its Applications

194 3 / Algorithms

of the terms of the sequence. To see this, note that the initial value of max is the first term of
the sequence; as successive terms of the sequence are examined, max is updated to the value
of a term if the term exceeds the maximum of the terms previously examined. This (informal)
argument shows that when all the terms have been examined, max equals the value of the largest
term. (A rigorous proof of this requires techniques developed in Section 5.1.) The algorithm
uses a finite number of steps, because it terminates after all the integers in the sequence have
been examined. The algorithm can be carried out in a finite amount of time because each step is
either a comparison or an assignment, there are a finite number of these steps, and each of these
two operations takes a finite amount of time. Finally, Algorithm 1 is general, because it can be
used to find the maximum of any finite sequence of integers. ▲

Searching Algorithms

The problem of locating an element in an ordered list occurs in many contexts. For instance, a
program that checks the spelling of words searches for them in a dictionary, which is just an
ordered list of words. Problems of this kind are called searching problems. We will discuss
several algorithms for searching in this section. We will study the number of steps used by each
of these algorithms in Section 3.3.
The general searching problem can be described as follows: Locate an element x in a list of
distinct elements a 1 ,a 2 ,...,a n , or determine that it is not in the list. The solution to this search
problem is the location of the term in the list that equals x (that is, i is the solution if x = a i )
and is 0 if x is not in the list.
THE LINEAR SEARCH The first algorithm that we will present is called the linear search,
or sequential search, algorithm. The linear search algorithm begins by comparing x and a 1 .
When x = a 1 , the solution is the location of a 1 , namely, 1. When x = a 1 , compare x with a 2 .If
x = a 2 , the solution is the location of a 2 , namely, 2. When x = a 2 , compare x with a 3 . Continue
this process, comparing x successively with each term of the list until a match is found, where
the solution is the location of that term, unless no match occurs. If the entire list has been
searched without locating x, the solution is 0. The pseudocode for the linear search algorithm
is displayed as Algorithm 2.

ALGORITHM 2 The Linear Search Algorithm.

procedure linear search(x: integer, a 1 ,a 2 ,...,a n : distinct integers)
i := 1
while (i ≤ n and x = a i )
i := i + 1
if i ≤ n then location := i
else location := 0
return location{location is the subscript of the term that equals x,oris0if x is not found}

THE BINARY SEARCH We will now consider another searching algorithm. This algorithm
can be used when the list has terms occurring in order of increasing size (for instance: if the
terms are numbers, they are listed from smallest to largest; if they are words, they are listed
in lexicographic, or alphabetic, order). This second searching algorithm is called the binary
search algorithm. It proceeds by comparing the element to be located to the middle term of
the list. The list is then split into two smaller sublists of the same size, or where one of these
smaller lists has one fewer term than the other. The search continues by restricting the search
to the appropriate sublist based on the comparison of the element to be located and the middle
term. In Section 3.3, it will be shown that the binary search algorithm is much more efficient
than the linear search algorithm. Example 3 demonstrates how a binary search works.