Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Example-Binary Search

 

Consider the problem of finding the position of an item in a sorted list. I.e., given the sorted sequence tex2html_wrap_inline68671 and an item x, find i (if it exists) such that tex2html_wrap_inline68677. The usual solution to this problem is binary search .

Binary search is a divide-and-conquer strategy. The sequence S is split into two subsequences, tex2html_wrap_inline68681 and tex2html_wrap_inline68683. The original problem is split into two subproblems: Find x in tex2html_wrap_inline68687 or tex2html_wrap_inline68689. Of course, since the original list is sorted, we can quickly determine the list in which x must appear. Therefore, we only need to solve one subproblem.

Program gif defines the function BinarySearch which takes four arguments, array, x, i and n. This routine looks for the position in array at which item x is found. Specifically, it considers the following elements of the array:

displaymath68669

   program32877
Program: Divide-and-Conquer Example--Binary Search

The running time of the algorithm is clearly a function of n, the number of elements to be searched. Although Program gif works correctly for arbitrary values of n, it is much easier to determine the running time if we assume that n is a power of two. In this case, the running time is given by the recurrence

  equation32885

Equation gif is easily solved using repeated substitution:

eqnarray32891

Setting tex2html_wrap_inline68699 gives tex2html_wrap_inline68701.


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.