Thread: Ornery binary search algorithm

Hi there. I am working on a relative file structure with a table index. I have a binary search algorithm to search the index for and input key but I am afraid this binary search has me stumped!
Any help would be much appreciated.
Jesse

int Search(char InputKey[])
{
FILE *Index;
int Relative;
int Start = 0;
int Middle;
long End = filelength(Index) / sizeof Address;
int Location = -1;


while ((Location = -1)&&(Start <= End))
{
Middle = ((Start + End) / 2) *sizeofFileAddress;
fseek(Index, Middle , SEEK_SET);
fread(&FileAddress, sizeof FileAddress, 1, Index);

if (strcmp(FileAddress.Key, InputKey) == 0)
Location = Middle * sizeof FileAddress;
else
if (strcmp(FileAddress.Key, InputKey) < 0)
Start = Middle + 1;
else
// if (strcmp(Car.chassis, InputKey) > 0)
End = Middle - 1;
}

if (Location = -1)
puts("\nRecord key does not exist.\n");
else
{
fseek(Index, Location, SEEK_SET);
Relative = ftell(Index);
}
getch();
return Relative;
}

'binary search' just means you are using a binary tree... It is a way to sort your index so that your access don't have to "hunt" for the data.


For example, let's say your database is an array of the following structures:

typedef struct
{
int field_1;
char field_2;
long field_3;
char field_4[50];
...
long field_34;
}record,*recordPtr;

Let's assume the above struct is 200 bytes in size. Furthermore, let's say that the array has 10 elements. 200 x 10 = 2000 bytes in size for the entire database.

Your index table, also called a 'hash' table, has entries that have the following format:

typedef struct hashStruct
{
struct hashStruct *left; /* left child */
struct hashStruct *right; /* right child */
recordPtr theRec; /* address of record */
long index; /* the index */
long filePos; /* where record starts in file */
}hashNode,*hashNodePtr;

Your hash table is sorted by the 'index' field. Each index is unique to the record it is associated with. Giving the record a certain 'weight'.

For example, if we arbitrarily say the first record added to the database has an index of '1', and the next '2', and the one following '3', and so on. We give each record a weight based on when it was added. We could then balance and sort the tree based on these unique indexes.

You use recursion to walk the tree structure. The root of the tree could be named 'rootP' and be a variable like so:

hashNodePtr rootP;

----

Since your database on disk, is just an array of structs that don't change position, you can search and sort quickly, because you've loaded each hashNode for each record with the records relative position in your file. The you can fseek by saying:

FILE *theFile;
hashNodePtr rootP;
hashNodePtr theNodeP;
record theR;

/* assume table and file already built */
/* further assume that 'theNodeP' has */
/* already been pointed to node in hash */
/* table that is of interest */

theFile = fopen("database","b");
fseek(theFile,theNodeP->filePos,0);
fread(&theR,sizeof(record),1,theFile);
fclose(theFile);
theFile = nil;

....

That should help.

hey

>>> if (Location = -1)
<<< if (Location == -1)

and

>>> while ((Location = -1)&&(Start <= End))
<<< while ((Location == -1)&&(Start <= End))

investigate the warnings that your compiler produces :-)

> while ((Location = -1)&&(Start <= End))

damyan is correct-- you are misusing the '=' operator.

'=' is for assigned: b = 5;
'==' is for comparison: is b == 5?