Implementing Binary Search on Random Access Files in Java

Question

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 1

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.