Probabilistic search - psearch.tar.gz ~~ possible proof of wrongness

[Hasan Aljudy]

Sean Kelly wrote:
> Hasan Aljudy wrote:
> 
>>
>> and here's the D code, according to what I understood of the algorithm.
>> if something is wrong in my understanding, please point me to it.
>>
>> ---------
>> import std.stdio;
>> import std.random;
>>
>> template psearch(T)
>> {
>>     bool psearch( T[] arr, T element )
>>     {
>>         if( arr.length == 1 )
>>         {
>>             if( arr[0] == element ) return true;
>>             else return false;
>>         }
>>
>>         int choice = rand() % 2;
>>
>>         T[] first, second;
>>         int middle = arr.length / 2;
>>
>>         if( choice == 1 )
>>         {
>>             first = arr[0..middle];
>>             second = arr[middle..$];
>>         }
>>         else
>>         {
>>             first = arr[middle..$];
>>             second = arr[0..middle];
>>         }
>>
>>         if( !psearch( first, element ) )
>>         {
>>             return psearch( second, element );
>>         }
>>         return false;
>>     }
>> }
> 
> 
> Thanks for posting this.  I hadn't taken the time to look at the 
> algorithm yet, and this got me interested :-)  The algorithm is 
> obviously O(N) for single-element searches, and equivalent in 
> theoretical complexity to the naive approach for substring searches.  In 
> practical terms it's even worse because of the N recursive function 
> calls, but it could always be rewritten as a loop with some bookkeeping.
> 
> It's obvious that the algorithm favors certain pattern positions in the 
> search string, ie. (1/4)N, (3/4)N, and so on, while traditional searches 
> typically perform best if the pattern is near the beginning of the 
> string.  Though this raises an interesting point--the probabilistic 
> search above is not a "find first" or "find last" algorithm.  Probably 
> not a big deal for unordered sets, but it might be otherwise.
> 
> 
> Sean


I think I have a mistake in the last bit of it ..

I wrote:

         if( !psearch( first, element ) )
         {
             return psearch( second, element );
         }
         return false;

when it should be:

         if( psearch( first, element ) )
         {
             return true;
         }
         else
         {
              return psearch( second, element );
         }