OpenEuphoria

Re: Searching Unsoted Lists

• Posted by Joe Phillips <bubba at TXWES.EDU> Mar 25, 1998
• 776 views

>
>How can you use a binary search on an unsorted list?
>
I just deleted about 50 minutes of typing because I realized that the
answer to your question is that you cannot.  I was referring to a list that
is not sorted physically, but rather logically with next and/or previous
pointers.

Sorry about the mis-statement. I was trying to point out that to scan n/2
pointers before comparing data, then again n/n/2 scans before comparison,
etc, can significantly decrease search time. But, most databases do not
have the linkage I am talking about. (At least not available to its own
development tools.)

If, however, you are building your own databases, then a linked file, or
key file, would not take any significant over-head to maintain.

You probable already know this, but for the beginners:

In a database record, you can have pointers which indicate the physical
record number (or physical byte offset) of the next logical record. Yes,
this requires programming maintenance, but it allows you to reuse records
that were deleted, not to have to rebuild the entire array/file when
inserting a record, etc.  (I use prev and next pointers to allow reverse
scanning.)

You can have as many pointers as you have keys.  Then, your key data is
stored in place in the record and derefenced only when a comparison is
needed.

An example record (Indexs can be modified to allow complex keys)

{Idx1 Field Num, prev, next},
{Idx2 Field Num,prev,next},
  ...
{Idx(n) Field Num,prev,next},
{field 1}
{field 2}
{field 3}
{field 4}
  ...
{field n}

I find it is easier and more effecient to rebuild linked lists than
rebuilding external index files. In some cases, I read the linked lists
into memory and do disk i/o only for key comparisons and in some cases I
build an index array in memory.

This whole scheme was back in the days of low memory, but it still serves
to keep data and indexes together.


--[ Joe Phillips, Sytems Analyst
--[ Texas Wesleyan University     817-531-4444
--[
--[  "The tongue of the just is as choice silver:
--[   the heart of the wicked is little worth."  Proverbs 10:20