OpenEuphoria

Re: binary search with reference to append

• Posted by jaygade Jun 13, 2014
• 1984 views

Untested:

-- Precondition: haystack is a list sorted in ascending order. 
--               If provided, startp and endp are less than or equal to 
--               haystack length and startp is less than or equal to endp. 
-- Returns: Index of needle in haystack, or 0 if not found. 
 
function bsearch(object needle, 
                 sequence haystack, 
                 integer startp=1, 
                 integer endp=0) 
 
    integer nItems, lo, hi, midp 
    --------------------- 
    nItems = length(haystack) 
    lo = max({1, startp}) 
 
    if endp > 0 and endp <= nItems then 
        hi = min({endp, nItems}) 
    else 
        hi = nItems 
    end if 
 
    -- We should provide a useful error message here, but crash is good 
    -- enough. 
    if hi > nItems or lo > hi then abort(1) end if 
 
    --------------------- 
 
    while lo <= hi do 
        midp = floor((lo + hi) / 2) 
        switch eu:compare(needle, haystack[midp]) do 
          case -1 then hi = midp - 1 
          case 0 then return midp 
          case +1 then lo = midp + 1 
        end case 
    end while 
 
    -- Not found. 
    return 0 
 
end function