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