# Binary Insert

### Insert a Value Directly into a Sorted Table

This function inserts a value into a sorted table via a binary search algorithm. It is faster than doing a regular table.insert(table, value) followed by a table.sort(table [, comp]).

```--[[
table.bininsert( table, value [, comp] )

Inserts a given value through BinaryInsert into the table sorted by [, comp].

If 'comp' is given, then it must be a function that receives
two table elements, and returns true when the first is less
than the second, e.g. comp = function(a, b) return a > b end,
will give a sorted table, with the biggest value on position 1.
[, comp] behaves as in table.sort(table, value [, comp])
returns the index where 'value' was inserted
]]--
do
-- Avoid heap allocs for performance
local fcomp_default = function( a,b ) return a < b end
function table.bininsert(t, value, fcomp)
-- Initialise compare function
local fcomp = fcomp or fcomp_default
--  Initialise numbers
local iStart,iEnd,iMid,iState = 1,#t,1,0
-- Get insert position
while iStart <= iEnd do
-- calculate middle
iMid = math.floor( (iStart+iEnd)/2 )
-- compare
if fcomp( value,t[iMid] ) then
iEnd,iState = iMid - 1,0
else
iStart,iState = iMid + 1,1
end
end
table.insert( t,(iMid+iState),value )
return (iMid+iState)
end
end
-- CHILLCODE™
```

Test suite:

```-- test: typical usage, with duplicates
t = {}
table.bininsert(t,  5)
assert(table.concat(t) == "5")
table.bininsert(t,  4)
assert(table.concat(t) == "45")
table.bininsert(t,  6)
assert(table.concat(t) == "456")
table.bininsert(t,  5)
assert(table.concat(t) == "4556")
table.bininsert(t,  6)
assert(table.concat(t) == "45566")
table.bininsert(t,  4)
assert(table.concat(t) == "445566")
table.bininsert(t,  0)
assert(table.concat(t) == "0445566")

-- test: fcomp
fcomp = function(a, b) return (a%3) < (b%3) end
t = {}
table.bininsert(t, 9, fcomp)
assert(table.concat(t) == "9")
table.bininsert(t, 3, fcomp)
assert(table.concat(t) == "93")
table.bininsert(t, 6, fcomp)
assert(table.concat(t) == "936")
table.bininsert(t, 2, fcomp)
assert(table.concat(t) == "9362")
table.bininsert(t, 7, fcomp)
assert(table.concat(t) == "93672")
table.bininsert(t, 1, fcomp)
assert(table.concat(t) == "936712")
table.bininsert(t, 5, fcomp)
assert(table.concat(t) == "9367125")
table.bininsert(t, 8, fcomp)
assert(table.concat(t) == "93671258")
table.bininsert(t, 4, fcomp)
assert(table.concat(t) == "936714258")
print "DONE"
```