Binary Search Specification

   
Recent changes
Table of contents
Links to this page
FRONT PAGE / INDEX
A page for putting a revised version of the specification for the binary search challenge. The original pages are: This is a lightly edited version of the "spec" page.

After much discussion elsewhere, perhaps this should no longer be called the binary search challenge. Perhaps the exact algorithm should remain unspecified, and just the O(log n) performance be required. That is, after all, what's actually being tested.

The following revised specification takes that approach.

Overview

Write a routine to implement a logarithmic search in a sorted array. Your routine will take a sorted array and a key, and return either the index of the first element that compares as equal to the key, or the value NotFound if no element compares as equal.

The Specification

Write a non-recursive 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 the element  Key
                       is not in the array.

The function cmp passed to routine find is your only means of comparing two things of type Object. This function is broadly 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:

If cmp(p,q)==0 then we say that p and q compare as equal. Loosely speaking, if cmp(&a,&b)<0 then we think of a as being "less than" b.

The array is sorted, so you know that if i and j are integers 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)==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. Please note that this example does not meet the specification. It is included here merely to demonstrate the usage of the parameters. 

 
    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;
    }

Contents

 

Links on this page

 
Site hosted by Colin and Rachel Wright:
  • Maths, Design, Juggling, Computing,
  • Embroidery, Proof-reading,
  • and other clever stuff.
Suggest a change ( <-- What does this mean?) / Send me email
Front Page / All pages by date / Site overview / Top of page

Universally Browser Friendly     Quotation from
Tim Berners-Lee 		    Valid HTML 3.2!