OpenEuphoria

Re: Language enhancement

• Posted by Joe Otto <jotto at NETZERO.NET> Jul 09, 1999
• 466 views

Thanks for the code Rod - I've already written a Euphoria version though.
       :)

What I'd like to see is the binary search algorithm implemented by Robert
*internally* like find () is.  That would give us access to VERY fast
searches.

Joe

-----Original Message-----
From:   Roderick Jackson [SMTP:rjackson at CSIWEB.COM]
Sent:   Friday, July 09, 1999 11:33 AM
To:     EUPHORIA at LISTSERV.MUOHIO.EDU
Subject:        Re: Language enhancement

>Robert,
>
>I think a very useful addition to Euphoria would be a function similar to
>find () as follows:
>
>        i = find_sorted (x, s)
>
>This function would assume that "s" is sorted and perform a binary search.
> I haven't done any benchmarking on this, but as I understand it, find ()
>only does a linear search because it does not take a sorted sequence.
> Correct?

That's correct. A binary search might actually be a nice addition; it
should
on average be much faster for large sequences. Maybe it could be put in the
misc.e file, or possibly sort.e.

In the meantime, this function (in case you needed one) should do the
trick:

 -- BEGIN CODE --

function sfind (object x, sequence s)

   integer min, max, pos, comp

   min = 1
   max = length (s)

   while (min <= max) do
      pos = min + floor ((max - min) / 2)
      comp = compare (s[pos], x)
      if (comp = 0) then
         return pos
      elsif (comp < 0) then
         min = pos + 1
      else
         max = pos - 1
      end if
   end while

   return 0

end function

 -- END CODE --

Hope this helps,


Rod Jackson
________________________________________________________
NetZero - We believe in a FREE Internet.  Shouldn't you?
Get your FREE Internet Access and Email at
http://www.netzero.net/download/index.html