Probabilistic search - psearch.tar.gz

[Nic Tiger]

this is your latest code, with proper comparisons counting and some 
simple test;
just compile it and run.
last printed line will state:
   average_cmp=247
which is essentially ~(N/2) for 512 item test

as a note, you should write compare(*(void**)base, element), otherwise 
it is difficult to use any of existing comparison functions (strcmp or 
smth.)

Nic Tiger.

-------- test suite for psearch --------
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

int comparisons = 0;

int compare (void *p1, void *p2) {
   comparisons ++;
   return strcmp ( *(const char**)p1, (const char*)p2 );
}

void *psearch(void *base, int size, int width, void *element, int 
(*compare)(void *, void *)) {
   static int depth = 0;

   if(size <= 1) {
     return ! size || compare(base, element) ? NULL : base;
   } else {
     int half, right;
     void *found;

     half = size / 2;
     right = abs(rand()) % 2;
     //comparisons = ++depth;
     if(right) {
       found = psearch((char*)base + half * width, size - half, width, 
element, compare);
       if(! found) {
         found = psearch((char*)base, half, width, element, compare);
       }
     }
     else {
       found = psearch((char*)base, half, width, element, compare);
       if(! found) {
         found = psearch((char*)base + half * width, size - half, width, 
element, compare);
       }
     }
     --depth;
     return found;
   }
}

main () {
   char *list[512];
   int i;
   for ( i = 0; i < 512; i ++ ) {
     char buf[32];
     sprintf ( buf, "str%d", i );
     list[i] = strdup(buf);
   }

   int total_cmp = 0;
   for ( i = 0; i < 512; i ++ ) {
     comparisons = 0;
     void *res = psearch ( list, 512, 4, list[i], compare );
     if ( res )
       printf ( "%d comparisons to find %s (found as %d index of 
list)\n", comparisons, list[i], (char**)res - list );
     else
       printf ( "%s not found, %d comparisons\n", list[i], comparisons );
     total_cmp += comparisons;
   }
   printf ( "average_cmp=%d", total_cmp/512 );
}