Discrete Mathematics for Computer Science

Binary Search 569

of elements is about half the size of the previously examined set. The process of dividing

the set in half and then ignoring half of the elements in the next step of the algorithm is

continued until it is determined that the element is or is not in the set.

INPUT: Array A[1.. n] with n elements in increasing order and an item X

to be sought in A

OUTPUT: If X is in A, its location is given in Found;

otherwise, Found = 0

BinSrch (A, X, 1, n) /* The initial call *1

BinSrch (A, Item, Left, Right) /* The recursive procedure */

1. if (Left > Right) then
   return 0
   else


2. Midpoint = [(Left + Right)/2J


3. if (Item = A[Midpoint]) then


4. return Midpoint
   else


5. if (Item < A[Midpoint]) then


6. BinSrch(A, Item, Left, Midpoint - 1)
   else


7. BinSrch(A, Item, Midpoint + 1, Right)

This is the same algorithm as the one used previously to find a Name in a phone

directory (see Section 1.10.4).

9.71 Correctness

To show that BinSrch terminates and returns the correct answer, a proof by induction can be
given. The proof of the inductive step is based on the following observations. First, notice
that the values of Left and Right have the property that for any execution of BinSrch where
Left < Right, either X is found (line 3) in A (Left) .... A (Right), the position of X in A is
returned, and the procedure terminates, or the value of one of Right and Left is changed. For
any execution of lines 1 through 4, in which X is not found in the middle of the elements
of A being considered, either (line 3) decreases Right by one or (line 4) increases Left by
one. Therefore, if the element X is not found, the values of Left and Right will eventually
satisfy the condition Left > Right in line 1, which will cause a value of zero to be returned
and the procedure to terminate. The correctness will follow from an induction on n, the
size of the ordered set being searched.