OpenEuphoria

Re: Language enhancement

• Posted by Roderick Jackson <rjackson at CSIWEB.COM> Jul 09, 1999
• 498 views

>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