[Back to FILES SWAG index]  [Back to Main SWAG index]  [Original]

{===========================================================================
 BBS: Canada Remote Systems
Date: 05-31-93 (20:29)             Number: 24331
From: HERB BROWN                   Refer#: NONE
  To: ERIC GIVLER                   Recvd: NO
Subj: USERS FILE                     Conf: (1221) F-PASCAL
---------------------------------------------------------------------------
On this day, <May 28 17:32>, Eric Givler (1:270/101.15@fidonet) noted:
 EG> How would this help?  You'd still have to search the entire
 EG> INDEX file LINEARLY, correct?  Or would you have the INDEX sorted?
 EG> If so, how would you keep it sorted?  More input would REALLY be
 EG> appreciated!

This is code for a binary "split and search" method.   Anyways, thats just
something I call it.  Actually, it's a rudimentary binary search.

Suppose you had a key record of                                           }

 key = record
 reference : Longint;  { room for a lot of records }
 KeySearchField : String30; { The key string to be stored}
 end;     { Note, several smaller strings could be put together to make the
            search critical, i.e., keysearchField:=First+second+ThirdName;
            As long as the field length stays less than or equal to what you
         defined }

{Then using a function that would return a boolean value, i.e., true if data
matches, false if not found, then it would look like so.. }

Function FindKey( VAR  AKey : AKeyFile;
                  VAR  AKeyRef : Longint;
                       FindMe : String80): Boolean;

VAR High,Low,Mid : Longint;  { For collision processing }
     Target : Key;
     Gotit  : Boolean;
     Collison : Boolean;
     NumRecs  : Longint;


begin
 AKeyRef :=0;
 NumRecs := FileSize(AKey);  {Get the number of records stored in file}

 High := NumRecs;
 Low := 0;
 Mid := (Low + High) DIV 2 { Split point }
 FindKey := False;
 Gotit := False;
 Collision := False;
 If NumRecs > 0 Then {the file is not empty }
  Repeat
   Seek(AKey,Mid);
   Read(Akey,Target);
   {Was there a position collision ??}
   IF (Low = Mid) OR (High = Mid) the Collision := True;
     IF Findme := Target.KeySearchField Then { Yay ! }
         begin
          Gotit := True;
          FindKey := True;
          AKeyRef := Target.Reference;
        End
    Else  { Divide in half and try it again..}
     Begin
      If FindMe > Target.KeySearchField then Low := Mid
       Else High := Mid;
      Mid := (Low + High + 1) DIV 2;
      AKeyRef := Mid
    End
 Until Collision or Gotit;
End;

(*
This is a working example.  There are some minor precautions that need to be
noted, though.   This will only work on sorted data, for one.  The data can be
sorted with a Quick Sort and the key file re-written in sorted order.   The
advantage here is the actual data file need not be sorted at all.

Any time you work with a data base, get into the habit of ALWAYS including a
deleted tag field.  The above example lacks this, though.

This is just one of many ways of searching a database.  Professional <grin>
applications would probably be better suited for AVL trees or Btrees.

Building an array "cache" helps speed up processing as well.  That is whole
'nuder ball game, though.. *)

[Back to FILES SWAG index]  [Back to Main SWAG index]  [Original]