News for hackers. Stuff that matters.
Re:Are you one of the 10% of programmers who can write a bin... by kragen on Monday April 19, 2010 @11:31PM (#1278547)
Mine is:

    -- find index of thing in sorted things in the range [first, last)
    function bsearch_2(things, thing, first, last)
       if first == last then return nil end
       assert(last > first)

       local midpoint = math.floor((first + last) / 2)
       assert(midpoint >= first)
       assert(midpoint < last)

       local test = things[midpoint]
       if test == thing then return midpoint end
       if test > thing 
       then return bsearch_2(things, thing, first, midpoint)
       else return bsearch_2(things, thing, midpoint+1, last)
       end
    end

    function bsearch(things, thing) 
       return bsearch_2(things, thing, 1, #things+1) 
    end
That's Lua, which uses 1-based indices. I'd be happy to hook up input-output stuff to it if you like.

There are no comments on this comment yet.