OpenEuphoria

Re: find function

• Posted by "Boehme, Gabriel" <gboehme at POSTOFFICE.MUSICLAND.COM> Oct 18, 1999
• 607 views

Mike,

Don't have the time to benchmark, but here's the binary search routine I
always use. I believe I got the basic idea from a QuickBasic textbook,
although the Euphoria implementation is my own. Enjoy!

Gabriel


global function find_sorted(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
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


-----Original Message-----
From: Mike [mailto:vulcan at WIN.CO.NZ]
Sent: Monday, October 18, 1999 2:29 PM
To: EUPHORIA at LISTSERV.MUOHIO.EDU
Subject: find function


Below is a function that can be used in place of Euphoria's find() IF the
list to be searched is sorted ( in ascending order).
I have written it to manage a word list for my windows editor ( which is
progressing slowly   ) but I thought that some may find it useful and
maybe someone could optimize it especially for a small list where find()
currently has the advantage. For any list the search time for almost all
elements is fairly constant regardless of where they are located. In the
case of a massive list where the element to be located is NOT near the start
of the list then this function really shows it's colours. I did have a look
at hash.ex and tree.ex in euphoria\demo but these do not suit my purpose and
may be be less "clean" to implement. I don't know if the name is appropriate
but there is a 'integer divide by 2' part in the code so I thought "What the
heck, why not!".

Any feedback is appreciated.

Yours Truly
Mike

vulcan at win.co.nz

global function binary_find(object element, sequence list)
 -- find element in list, same as find()
 integer start, finish, low, high, range, jump, d

 start=1
 finish=length(list)

 low=start
 high=finish

 while 1 do
  range=high - low

  if range < 2 then
   d = find(element, list[low..high])
   if d then d += low - 1 end if
   return d
  else
   jump=floor(range/2)
   d=compare(element, list[low + jump])

   if d=1 then -- search higher
    low += jump
    if low > finish then
     return 0
    end if
   elsif d=-1 then -- search lower
    high=low + jump
   else -- a hit!
    return low + jump
   end if
  end if
 end while
 return 0
 end function