Binary Search
 

News:

29 December 2022 - PtokaX 0.5.3.0 (20th anniversary edition) released...
11 April 2017 - PtokaX 0.5.2.2 released...
8 April 2015 Anti child and anti pedo pr0n scripts are not allowed anymore on this board!
28 September 2015 - PtokaX 0.5.2.1 for Windows 10 IoT released...
3 September 2015 - PtokaX 0.5.2.1 released...
16 August 2015 - PtokaX 0.5.2.0 released...
1 August 2015 - Crowdfunding for ADC protocol support in PtokaX ended. Clearly nobody want ADC support...
30 June 2015 - PtokaX 0.5.1.0 released...
30 April 2015 Crowdfunding for ADC protocol support in PtokaX
26 April 2015 New support hub!
20 February 2015 - PtokaX 0.5.0.3 released...
13 April 2014 - PtokaX 0.5.0.2 released...
23 March 2014 - PtokaX testing version 0.5.0.1 build 454 is available.
04 March 2014 - PtokaX.org sites were temporary down because of DDOS attacks and issues with hosting service provider.

Main Menu

Binary Search

Started by Mogli, 02 July, 2005, 10:44:40

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Mogli

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

SMF spam blocked by CleanTalk