Page 216 - Discrete Mathematics and Its Applications

3.1 Algorithms 195

EXAMPLE 3 To search for 19 in the list

123567810 12131516181920 22,

first split this list, which has 16 terms, into two smaller lists with eight terms each, namely,

123567810 12131516181920 22.

Then, compare 19 and the largest term in the first list. Because 10 < 19, the search for 19 can
be restricted to the list containing the 9th through the 16th terms of the original list. Next, split
this list, which has eight terms, into the two smaller lists of four terms each, namely,

12 13 15 16 18 19 20 22.

Because 16 < 19 (comparing 19 with the largest term of the first list) the search is restricted to
the second of these lists, which contains the 13th through the 16th terms of the original list. The
list 18 19 20 22 is split into two lists, namely,

18 19 20 22.

Because 19 is not greater than the largest term of the first of these two lists, which is also 19, the
search is restricted to the first list: 18 19, which contains the 13th and 14th terms of the original
list. Next, this list of two terms is split into two lists of one term each: 18 and 19. Because
18 < 19, the search is restricted to the second list: the list containing the 14th term of the list,
which is 19. Now that the search has been narrowed down to one term, a comparison is made,
and 19 is located as the 14th term in the original list. ▲

We now specify the steps of the binary search algorithm. To search for the integer x in the
list a 1 ,a 2 ,...,a n , where a 1 <a 2 < ··· <a n , begin by comparing x with the middle term a m
of the list, where m = (n + 1)/2 . (Recall that x is the greatest integer not exceeding x.) If
x> a m , the search for x is restricted to the second half of the list, which is a m+1 ,a m+2 ,...,a n .
If x is not greater than a m , the search for x is restricted to the first half of the list, which is
a 1 ,a 2 ,...,a m .
The search has now been restricted to a list with no more than n/2 elements. (Recall that
x is the smallest integer greater than or equal to x.) Using the same procedure, compare x to
the middle term of the restricted list. Then restrict the search to the first or second half of the
list. Repeat this process until a list with one term is obtained. Then determine whether this term
is x. Pseudocode for the binary search algorithm is displayed as Algorithm 3.

ALGORITHM 3 The Binary Search Algorithm.

procedure binary search (x: integer, a 1 ,a 2 ,...,a n : increasing integers)
i := 1{i is left endpoint of search interval}
j := n {j is right endpoint of search interval}
while i< j
m := (i + j)/2
if x> a m then i := m + 1
else j := m
if x = a i then location := i
else location := 0
return location{location is the subscript i of the term a i equal to x,or0if x is not found}