OpenEuphoria

Re: stdlib: Binary search function

• Posted by egg <egege at ramble??ru> May 21, 2008
• 659 views

integer found   --flag

function findPos(sequence s, sequence ss)
  --bynary search in a sorted array of strings
  --it returns position of found string or position where it could be iserted
  --which one is found we know by the flag

  integer lo,hi,mid,c
  lo = 1
  hi = length(ss)
  
  c = compare(s,ss[1])
  if c<0 then
    found = 0
    return 1
  elsif not c then
    found = 1
    return 1
  end if
  
  c = compare(s,ss[hi]) 
    if c>0 then
    found = 0
    return hi+1
  elsif not c then
    found = 1
    return hi
  end if  

  while 1 do
    w = hi - lo
    if not w then
      found = 0
      return hi
    elsif w<10 then
      lo += 1
      while 1 do
        c = compare(s,ss[lo])
        if not c then
          found = 1
          return lo
        elsif c<0 then
          found = 0
          return lo
        else
          lo += 1
        end if
      end while
    else  --(hi-lo)>=10
      mid = floor((lo + hi) / 2)
      c = compare(s,ss[mid])
      if c<0 then -- x < ss[mid]
        hi = mid
      elsif c>0 then  -- x > ss[mid]
        lo = mid
      else      -- x = ss[mid]
        found = 1
        return mid
      end if
    end if
  end while
end function  --findPos