I hope I can explain the way of searching
a normal table through binary search,
first we have a sorted normal table e.g.
t = {
[1] = 'a',
[2] = 'b',
[3] = 'c',
[4] = 'd',
[5] = 'e',
[6] = 'f',
[7] = 'g',
[8] = 'h',
[9] = 'i',
[10] = 'j',
}
now if would want to know if we have the char 'b'
in our table we can either run through the table
e.g.
for i,v in pairs( t ) do
if v == 'b' then
return i
end
end
but that is slower compared to the binary search
especially when haveing many table entries.
So we would search binary, by checking the entrie
in the middle
imid = math.floor( table.getn(t)/2 )
imid is in our case 5
then we check the item
if t[imid] == 'b' then
return imid
-- now we compare the item if its bigger or smaller
-- cause then we know it is either in the upper
-- lower half
if t[imid] > 'b' then
-- now we know b must be if its there in the upper half
-- nex imid is between 1 and imid
imid = math.floor( imid/ 2)
if t[imid] < 'b' then
-- b must be in the upper part if
imid = math.floor( ( table.getn( t ) + imid ) / 2 )
end
so let's try to find 'c'
first we get t[5] and its bigger so we know its in the
upper part, then we check t[2] here we know its smaller than 'c', so we know it can only be between t[2] and t[5]
then we would get t[3] and we have our 'c'
I hope you get the idea, this search is very fast
when x are the numbers of searches and n the number of table entries then, the search follows this equatation
n = 2^x
or number of searches used for n entries
x = log(n) / log(2)
where log is the logarithm to the basis 10
so if we have 1024 entries we only need 10 searches
whereas in the normal or linear search, you need
averagly as many searches as half of the table entries
x = table.getn( t ) / 2
so for 1024 entries we need 512 searches average