OpenEuphoria

Re: database theory

• Posted by Lucius Hilley III <lhilley at CDC.NET> Nov 24, 1998
• 748 views

On Mon, 23 Nov 1998 08:53:56 -0500, Irv Mullins <irv at ELLIJAY.COM> wrote:

  <SNIP>
Below is in reference to Binary Searches.
>   Strange as it may sound, it only takes a few (8?) steps
>   to locate the matching entry(s) in any file, regardless
>   of how long it may be. This method is very fast, and
>   can be written recursively, so there's not much code to
>   test.
>
>   Regards,
>   Irv

    Excuse me but this magic number of (8) is driving me
nuts.  There is an exact math as to maximum number of
tests will be required to find an entry.  It isn't
called binary searching for no reason.

Only 8 tests will search a maximum of 255 entries.
Now I no that both sounds rather limiting and also
rather amazing.  BUT the math follows as such.
Just one more test.  Say 9 tests will search a
maximum of 511 entries.  Notice! The number
practically doubled.

A database of 65,535 entries can be searched with
no more than 16 tests.  Here is a simple table.

TESTS = Max # of tests required
ENTRIES = # of Entries that can be searched.

TESTS  ENTRIES
1        1
2        3
4        15
8        255
16       65,535
32       4,294,967,295

    I hope you now grasp the power of binary searches.
I doubt you will ever require 32 tests for your
sorted database.
    Of course for binary searches to work the database
must be sorted at some level.
_________________________

Lucius L. Hilley III    lhilley at cdc.net
http://www.cdc.net/~lhilley
http://www.americanantiques.com
http://www.dragonvet.com
_________________________