Probabilistic search - psearch.tar.gz

[sundaresh]

Sorry about that, you were right, for all but the base case, the value of
comparisons is incremented in the else part. So here is the corrected version.
But the search time is still O(lg(n)), since avg comparisons is just one more
at 10,and I think the worst case comparisons is 11, so this still seems to be
comparable to binary search.Here is the corrected version.

#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) {
++comparisons;
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(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;
}
}


In article <e0uug0$2mq8$1 at digitaldaemon.com>, kwilson at nowhere.com says...
>
>Hi there Sandresh,
>
>The "bug" within your program is simply that your base case (or terminating
>case) for the recursion is (size == 1) and you increment/decrement a variable
>(ie. depth)  outside of this base case "if" statement. 
>
>This leads to a recursively maximized value of 9 (or log base 2 of 512), as
>pointed out. Then, since no variable is updated in the base case "if" statement,
>you don't actually add to the comparison total accordingly. Thus you mistakenly
>get a maximal depth of 9 for each search. This is not actually the depth to find
>the element you are searching for, but rather the depth to the "size == 1" base
>case.
>
>Now you will say that "this is not true" since the base case is reached many
>times during the search process before the search is terminated....not just once
>after depth equals nine. The static "depth" variable is not being updated
>properly, though.
>
>Once you try the changes suggested below you will see that the "Average depth"
>of the 2048 searches per distribution will be approximately 256. Single "depths"
>or comparisons will range from 1 to 512 as would be expected. The average per
>distribution is approximately N/2 as several others in this thread have pointed
>out, as the correct average case search for an element in a randomized array of
>size N. If you want to argue that the "depth" of the actual comparisons never
>exceeds 9, then that is obviously true because log base 2 of 512 is 9.....but
>that doesn't mean that the number of comparisons is 9. Sorry ;)
>
>Hope the code change and viewing the results will clear things up if anyone
>can't follow my explanation above (my fault for not explaining things well
>enough, I'm afraid).
>
>
>Try these simple changes:
>
>in psearch.c 
>
>on line 9:
>add ------>  ++comparisons;
>
>
>on line 18:
>comment out --------> //comparisons = ++depth;
>
>
>on line 31:
>comment out --------> //--depth;
>
>Thanks,
>K.Wilson
>
>
>
>
>