Author Topic: Binary Search  (Read 1247 times)

0 Members and 1 Guest are viewing this topic.

Offline Mogli

  • Fulll Member
  • ****
  • Posts: 59
  • Karma: +0/-0
Binary Search
« on: 02 July, 2005, 10:44:40 »
I hope I can explain the way of searching
a normal table through binary search,

first we have a sorted normal table e.g.

Code: [Select]
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.

Code: [Select]
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

Code: [Select]
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
« Last Edit: 02 July, 2005, 10:45:48 by Mogli »

PtokaX forum

Binary Search
« on: 02 July, 2005, 10:44:40 »