Binary Search Specification 


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.
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:
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.
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 

Quotation from Tim BernersLee 