Discrete Mathematics for Computer Science

78 CHAPTER 1 Sets, Proof Templates, and Induction

that could possibly contain the name. If the name is not on the middle page, the search

continues either in the first half of the pages being considered or in the last half of the pages

being considered. This strategy is just what BinarySearch does by repeatedly halving the

range of pages that it thinks could contain the name. Eventually, the process comes to a

page that must either contain the name or the process knows that the name does not occur

in the phone book.

INPUT: Name to be found in the phone directory City

OUTPUT: Message indicating whether or not Name was found

BinarySearch(Name, City)

FirstPage = the page number of the first page of City

LastPage = the page number of the last page of City

PageFound = FALSE

NameFound = FALSE

while (FirstPage < LastPage and PageFound = FALSE) do

MiddlePage = [(FirstPage + LastPage)/2]

if (Name falls between the first name on page MiddlePage

and the last name on page MiddlePage) then

PageFound = TRUE

else

if (Name is alphabetically less than

the first name on page MiddlePage) then

LastPage = MiddlePage - 1

else

FirstPage = MiddlePage + 1

if (PageFound = TRUE) then

Examine all names on page MiddlePage

if (Name is found on MiddlePage) then

NameFound = TRUE

else

NameFound = FALSE

if (NameFound = TRUE) then

Print a message saying Name is on MiddlePage

else

Print a message saying Name is not in City

Example 4. Determine whether Joe Smith is in a phone book with 521 pages. For this

problem, suppose Joe Smith appears on page 326.