Probabilistic search - psearch.tar.gz

[Nic Tiger]

sundaresh wrote:
> #include<stdlib.h>
> 
> int comparisons;
> 
> void *psearch(void *base, int size, int width, void *element, int
> (*compare)(void *, void *)) {
> static int depth = 0;
> 
> if(size <= 1) {

Replace this line
> ++comparisons;
with
   if ( size ) ++comparisons;

> return ! size || compare(base, element) ? NULL : base;
> }
> else {
> int half, right;
> void *found;
> 
> half = size / 2;
> right = abs(rand()) % 2;

and remove this line
> comparisons = ++depth;

> if(right) {
> found = psearch(base + half * width, size - half, width, element, compare);
> if(! found) {
> found = psearch(base, half, width, element, compare);
> }
> }
> else {
> found = psearch(base, half, width, element, compare);
> if(! found) {
> found = psearch(base + half * width, size - half, width, element, compare);
> }
> }
> --depth;
> return found;
> }
> }

then you will have *REAL* count of compare() function call
even better we to supply test compare function that would increment 
comparisons before returning comparison result.

If you don't apply mentioned changes, your code will count something 
completely different from "comparison number"

Nic Tiger