Probabilistic search - psearch.tar.gz

[sundaresh]

I believe that I have replied to this already. My first suspisions was with
comparisons, but there is nothing wrong with it. Comparisons is updated prior
to call to the base case psearch, so why should it be updated again during the
base case, since in the base case, no recursive call to psearch is being made.
Doing so might actually result in 256 or so as you claim, but that would be
introducing a bug and not eliminating it. Sorry, these arguments have only
served to convince me even further of the correctness and workability
of this algorithm.

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