Re: database theory
- Posted by Lucius Hilley III <lhilley at CDC.NET> Nov 24, 1998
- 593 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 _________________________