OpenEuphoria

Re: binary search with reference to append

• Posted by jaygade Jun 13, 2014
• 2003 views

I've edited my code several times but I think it's still not perfect.

This is better. Still 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) 
 
    if endp = 0 then 
        hi = nItems 
    else 
        hi = endp 
    end if 
 
    if hi <= nItems and startp <= hi then 
        lo = startp 
    else 
        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 

If startp > endp, but both are less than nItems, I think that either failure OR returning 0 is a valid response so long as it's documented. Failure could be better during debugging in order to catch invalid inputs when reasonable.

In this case it is reasonable to check the boundaries of the search, but it is not necessarily reasonable to check to see if the haystack is sorted.

This illustrates that the caller should validate the data before sending it to the bsearch function, and that the bsearch function should reject invalid inputs.