Suggest a change

These fields are all optional and need only
be supplied if you would like a direct reply.

Subject
Your email address
Your real name

You must answer this!

If you don't, my spam filtering will
ensure that I never see your email.

What's 8 plus five (in digits only)?

Please make your changes here and then
Editing tips and layout rules.

File: BinarySearchSpecification

A page for putting a revised version of the specification
for the binary search challenge.  The original pages are:
  * https://www.solipsys.co.uk/b_search/spec.htm
  * https://www.solipsys.co.uk/b_search/coding.htm
  * https://www.solipsys.co.uk/b_search/submit.htm

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:
  *  *cmp* always returns one of the values *-1*, *0* or *1*,
  *  *cmp(p,p)*=*0*,
  *  *cmp(p,q)*=*-cmp(q,p)*,
  *  *cmp(p,q)<=0*  and  *cmp(q,r)<=0*  together imply
      that  *cmp(p,r)<=0*.

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