## binary search

### Data

in lua

#### Tags

recursion, search

### Source Code

``````-- A binary search function implementation
local function bisect(t,v,comp,s,e)
s, e = s or 1, e or #t
if not s or e < s then return end
len = s - e + 1
local h = math.floor((s + e) / 2)
if t[h] == v then return h end
if not comp(t[h],v) then
return bisect(t, v, comp, s, h - 1)
else
return bisect(t, v, comp, h + 1, e)
end
end

-- Usage: f(tbl, value [,comp])
-- tbl: the table where to search, must be sorted
-- value: the value to be searched
-- comp (optional): a comparison function,
--  		 defaults to function(a,b) return a<b end
-- returns: the key if value was found, or nil
return function (tbl, value, comp)
comp = comp or function(a,b) return a < b end
return bisect(tbl, value, comp)
end``````
``````-- Tests for binary_search.lua
local binary_search = require 'binary_search'

local total, pass = 0, 0

local function dec(str, len)
return #str < len
and str .. (('.'):rep(len-#str))
or str:sub(1,len)
end

local function run(message, f)
total = total + 1
local ok, err = pcall(f)
if ok then pass = pass + 1 end
local status = ok and 'PASSED' or 'FAILED'
print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

run('Performs a binary search', function()
local t = {1, 2, 3, 4, 5}
assert(binary_search(t, 1) == 1)
assert(binary_search(t, 2) == 2)
assert(binary_search(t, 3) == 3)
assert(binary_search(t, 4) == 4)
assert(binary_search(t, 5) == 5)
end)

run('Array values do not have to be consecutive',function()
local t = {1, 3, 5, 10, 13}
assert(binary_search(t, 1) == 1)
assert(binary_search(t, 3) == 2)
assert(binary_search(t, 5) == 3)
assert(binary_search(t, 10) == 4)
assert(binary_search(t, 13) == 5)
end)

run('But the array needs to be sorted',function()
local t = {1, 15, 12, 14, 13}
assert(binary_search(t, 13) == nil)
assert(binary_search(t, 15) == nil)
end)

run('In case the value exists more than once, it returns any of them',function()
local t = {1, 12, 12, 13, 15, 15, 16}
assert(binary_search(t, 15) == 6)
assert(binary_search(t, 12) == 2)
end)

run('Accepts comparison functions for reversed arrays',function()
local t = {50, 33, 18, 12, 5, 1, 0}
local comp = function(a, b) return a > b end
assert(binary_search(t, 50, comp) == 1)
assert(binary_search(t, 33, comp) == 2)
assert(binary_search(t, 18, comp) == 3)
assert(binary_search(t, 12, comp) == 4)
assert(binary_search(t,  5, comp) == 5)
assert(binary_search(t,  1, comp) == 6)
assert(binary_search(t,  0, comp) == 7)
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
:format(total, pass, total-pass, (pass*100/total)))
``````