OpenEuphoria

Re: bfind.e / orphaned code?

• Posted by Robert Craig <rds at RapidEuphoria.com> Feb 08, 2006
• 431 views

Kenneth Rhodes wrote:
> I finally located this file on Jiri Babor's site.  I really wish
> that it was in the archive - Gabriel Boehme, Jiri Babor, Joe Otto,
> and Luscious Hilley have not been active on the list for several
> years. If Rob feels its appropriate, I'd like him to post it
> in the archives: 
> 
> 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
> 
> Luscious Hilley posted this to the list several years earlier:
> 
> ----bfind.e
> global function bfind(object this_in, sequence that)
>   integer min, max, gtlt, here
> 
>   min = 0
>   max = length(that)
>   here = floor((max / 2) + .5)
>   while min != max do
>     gtlt = compare(this_in, that[here])
>     if gtlt = 0 then
>       return here
>     elsif gtlt = 1 then
>       min = here
>       here = floor(((min + max) / 2) + .5)
>     else
>       max = here
>       here = floor(((min + max) / 2) + .5)
>     end if
>   end while
> 
>   return 0
> end function

I think whoever is working on the Euphoria Standard Library
should include this somewhere. I agree that a standard
binary search would be useful. Maybe I'll eventually add it
to euphoria\include somewhere.

Regards,
   Rob Craig
   Rapid Deployment Software
   http://www.RapidEuphoria.com