Specification

Overview

Write a routine to implement the binary search algorithm. Your routine will take a sorted array, a pointer to a key, and return either the index of the first occurrence of (a copy of) the key in the array, or the value   NotFound   if the element is not in the array.

The algorithm

This routine is given a sorted array, possibly with repetitions, and an element to find in the array. It proceeds by comparing the key with the element in the middle of the array. Based on the result of this comparison it can reject half of the array and continue. Eventually there is only one possibility left.

Simple analysis shows that if there are n elements in the array then this routine takes   O(log n)  operations.

The Specification

Write a non-recursive binary search routine in C. The prototype for the routine is 

    int find( Object Array[],
              int n,
              Object *KeyPtr,
              int (*cmp)(Object *, Object *),
              int NotFound
            );

In this prototype the arguments are as follows: 

    Object Array[] : An array of elements of type  Object.
                       You know nothing more about these.

    int n          : The number of elements in the array.
                       Note: the array is indexed from 1,
                       so that if 1 <= i <= n  then
                       element  A[i]  exists.

    Object *KeyPtr : Pointer to the Object to be found.

    int (*cmp)(Object *, Object *) : See below.

    int NotFound   : This is the value to be returned by
                       the routine if no element of the
                       array compares as equal to the Key.

The function cmp passed in to routine find is your means of comparing the sizes of two things of type Object. This function is similar to the function strcmp, and has the following properties.

If p, q and r all point to things of type Object, we have the following facts:

The array is sorted, so you know that for all integers i and j such that 0<i<=j<=n we have 

        cmp( &Array[i] , &Array[j] ) <= 0
or, equivalently, 

        cmp( Array+i , Array+j ) <= 0

If there is some index i such that cmp(&Array[i],KeyPtr) returns 0 then routine find must return the smallest such index. If no such index exists then routine find must return the given value NotFound. Routine find must make no more than (int)(log(n+1)/log(2)+2) calls to function cmp.

Comments

Below is a linear search program demonstrating the calling convention and use of comparisons, etc. It is included here merely to demonstrate the usage of the parameters.

THIS EXAMPLE DOES NOT
MEET THE SPECIFICATION! 

     int find( Object Array[], int n, Object *KeyPtr,
               int (*cmp)(Object *, Object *),
               int NotFound
              ) {
       int i;
       for (i=n;i>=1;i--)
           if (cmp(&Array[i],KeyPtr)==0)
               return i;
       return NotFound;
     }

Go to main page
How to submit an entry
Last modified: 2008/05/16 CDW