#!/usr/bin/lua
-- http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/

-- Apparently I am one of the 10%, because this code worked the first
-- time I tested it. It took me nine minutes to write and test.
-- > print(loadfile("bsearch.lua"))
-- function: 0x8865890
-- > loadfile("bsearch.lua")()
-- > print(bsearch({3, 5, 8, 11}, 8))
-- 3
-- > print(bsearch({3, 5, 8, 11}, 5))
-- 2
-- > print(bsearch({3, 5, 8, 11}, 3))
-- 1
-- > print(bsearch({3, 5, 8, 11}, 11))
-- 4
-- > print(bsearch({3, 5, 8, 11}, 12))
-- nil
-- > print(bsearch({3, 5, 8, 11}, 10))
-- nil
-- > print(bsearch({3, 5, 8, 11}, 1))
-- nil

-- I think this is a good task to use to teach thinking in terms of
-- formal logic.

-- 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