OpenEuphoria

Re: stdlib: Binary search function

• Posted by CChris <christian.cuvier at agri?ul?ure.gouv.fr> May 21, 2008
• 671 views

Kenneth Rhodes wrote:
> 
> CChris wrote:
> > 
> > 
> > This has been an oft requested functionality, and was in principle agreed,
> > even
> > by Rob:
> > <a
> > href="http://www.openeuphoria.org/cgi-bin/esearch.exu?fromMonth=6&fromYear=1&toMonth=5&toYear=D&postedBy=&keywords=binary_find">http://www.openeuphoria.org/cgi-bin/esearch.exu?fromMonth=6&fromYear=1&toMonth=5&toYear=D&postedBy=&keywords=binary_find</a>
> > <a
> > href="http://www.openeuphoria.org/cgi-bin/esearch.exu?fromMonth=6&fromYear=1&toMonth=5&toYear=D&postedBy=&keywords=bfind">http://www.openeuphoria.org/cgi-bin/esearch.exu?fromMonth=6&fromYear=1&toMonth=5&toYear=D&postedBy=&keywords=bfind</a>
> > 
> > Some implementations have been mentioned already (G. Boehme, J. Babor,...).
> > 
> > Now, the devil is in the details. What shall the function do?
> > * accept only strictly increasing sequences
> > * accept only strictly monotoni sequences
> > * accept loosely monotonic sequences (with possible duplicates)
> > * only cope with <any selection above>, not checking
> > 
> > I think everyone agrees it should return like db_find_key(), ie n>0 when
> > found,
> > n<0 with ordered insertion resulting in item lading at position -n.
> > 
> > And another point which wasn't agreed upon: would this go to sort.e or
> > sequence.e?
> > 
> > The version I use in sets.e has a from and to extra parameters. They could
> > be
> > easily defaulted. Monoony could be passed as a parameter too, depending on
> > the
> > option chosen.
> > 
> > CChris
> 
> Well, if the Devil is in the details, lets see the details. 
> Babor, Boehme, and Otto's bfind is short sweet and simple.
> 
> 
> }}}
<eucode>
> global function bfind(object x, sequence s)
> -- does a binary search on a sorted sequence
> -- returns index location if found, 0 if not
> -- assumes that sequence s has been sorted prior to this call
> -- Gabriel Boehme's code
> -- Earlier Joe Otto's routine is almost identical.
> integer lo, hi, mid, c
>    lo = 1
>    hi = length(s)
> 
>    while lo <= hi do
>       mid = floor((lo + hi) / 2)
>       c = compare(x, s[mid])
>       if    c < 0 then  -- x < s[mid]
>          hi = mid - 1
>       elsif c > 0 then  -- x > s[mid]
>          lo = mid + 1
>       else              -- x = s[mid]
>          return mid
>       end if
>    end while
> 
>    return 0
> end function
> </eucode>
{{{

> 
> It sounds as though your binary find may be a bit of
> a swiss army knife approach. Please post your bfind
> code from sets.e and let us play arround with it--
> But if there are many details, there might be more Devils!
> 
> 
> Ken Rhodes
> Folding at Home: <a
> href="http://folding.stanford.edu/">http://folding.stanford.edu/</a>
> 100% MicroSoft Free
> SuSE Linux 10.3
> No AdWare, SpyWare, or Viruses!
> Life is Good,  

The bfind() I use (can posy it only tonight) only assumes sorted sequences
without duplicates, as that's all it needs, and haas extra parms (lo and hi in
the above code).

Given the discussions referenced above, is this enough?

I forgot to mention: according to whether you expect hits to be more frequent
than misses, or the other way round, you can tweak the algorithm differently for
more overall speed.

In the routine you posted, if the sequence is not sorted, which is not checked,
results are undefined (but there is a result).

CChris