useruser123 useruser123 - 2 months ago 20
Java Question

Implementing Binary Search on Random Access Files in Java

I am doing a program in Java where the user can create "databases" (.txt files) using random access files and store records there. I am working on implementing Binary Search in order to give the user the option to find a record by ID.

public static String binarySearch(String fileName, String id,String data_config) throws IOException
{
RandomAccessFile Din = new RandomAccessFile(fileName, "r");
num_records = getNumOfRecords(data_config);
int Low = 0;
int High = num_records;
int Middle;
String MiddleId;
String record = "NOT_FOUND";
boolean Found = false;

while (!Found && (High >= Low))
{
Middle = (Low + High) / 2;

record = getRecord(fileName,Middle,data_config);
MiddleId = record.substring(0,3);
int result = MiddleId.compareTo(id);


if (result == 0) // ids match
Found = true;
else if (result < 0)

Low = Middle + 1;

else

High = Middle -1;

}
return record;
}


Here is the getRecord() method which works fine because I have tested it even without the binarySearch()method.

public static String getRecord(String fileName, int recordNum, String data_config) throws IOException
{
RandomAccessFile Din = new RandomAccessFile(fileName, "r");
num_records = getNumOfRecords(data_config);
String record = "NOT_FOUND";
if ((recordNum >=1) && (recordNum <= num_records))
{

Din.seek(0); // return to the top fo the file
Din.skipBytes(recordNum * record_size);
record = Din.readLine();
}

return record;
}


The problem is at the compareTo()method used in binarySearch. It always returns -1, satisfying the second part of the if-else statement.
For example, these are the records in one of my files:

Id Experience Married Wage Industry

0001 1 no 123.0 kjasdhsjhjh

0002 1 yes 123.0 asdhajshjasdhja

0003 1 yes 124.0 ajskjkasjd

0004 1 yes 124.0 kasjdkjsdjs

0005 1 yes 124.0 kajskdjaksdjkas

0006 1 yes 123.0 kjksjdkasj

If I search for 0001:

High = num_records = 5;

Low = 0, Therefore Middle =5/2 = 3

It goes to the third record and it runs 0003 compareTo(0001). The result of this comparison is -1. Since it is less than 0, new Low is equal to Middle + 1 = 3+1 = 4, and it goes to check the fourth record even though it shouldn't. Since it is binary search, in this case it is supposed to check the second record because 0001 is less than 0003.

Could you please help me find what I have done wrong here?

Answer

Check this: https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#substring%28int,%20int%29

When your record starts with 0003, record.substring(0,3); will return 000, not 0003. You should use record.substring(0,4); to get the id.