Probabilistic search - psearch.tar.gz

[BCS]

Andrew Fedoniouk wrote:
> 
> Lets assume that here unordered set (string) has flat distribution of 
> element(chars) occurences.
> 
> You can cry, pray, read C++ books, whatever you like, but it will take you 
> N/2 comparisons average
> and in the worst case N comparisons to find first occurence of something 
> there.
> 
> The only thing which affect N/2 average is the quality of your random 
> generator (flatness of distribution).
> And this quality is usual reason of "wonders" in such discoveries.
> 
> Andrew Fedoniouk.
> http://terrainformatica.com
> 

That is true if you are using N for the size of your alphabet

consider:

B is a string of random bits with even distribution of 1 or 0.

Find the first 1 bit.

mean search length is something like 1-2