Implementieren der binären Suche in wahlfreien Zugriffsdateien in Java

Question

Ich mache ein Programm in Java, wo der Benutzer "Datenbanken" (TXT-Dateien) erstellen kann, indem er Dateien mit wahlfreiem Zugriff verwendet und Datensätze dort speichert. Ich arbeite an der Implementierung der binären Suche, um dem Benutzer die Möglichkeit zu geben, einen Datensatz nach ID zu finden.

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; 
} 

Hier ist die GetRecord() Methode, die gut funktioniert, weil ich es auch ohne die binarysearch() Methode getestet haben.

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; 
} 

Das Problem ist am compareTo (Methode) in binarysearch verwendet. Es gibt immer -1 zurück und erfüllt den zweiten Teil der if-else-Anweisung. Zum Beispiel sind dies die Aufzeichnungen in einer meiner Dateien:

Id Erfahrung Verheiratet Lohn Industrie
0001 1 Nr 123,0 kjasdhsjhjh
0002 1 ja 123,0 asdhajshjasdhja
0003 1 ja 124,0 ajskjkasjd
0004 1 ja 124,0 kasjdkjsdjs
0005 1 ja 124,0 kajskdjaksdjkas
0006 1 ja 123,0 kjksjdkasj

Wenn ich für 0001 zu suchen:

Hoch = num_records = 5;

Low = 0, daher Mitte = 5/2 = 3

Es geht in der dritten Platte und es läuft 0003 compareTo (0001). Das Ergebnis dieses Vergleichs ist -1. Da es kleiner als 0 ist, ist New Low gleich Middle + 1 = 3 + 1 = 4, und es geht um den vierten Record zu überprüfen, obwohl es nicht sollte. Da es sich um eine binäre Suche handelt, sollte in diesem Fall der zweite Datensatz überprüft werden, weil 0001 kleiner als 000 ist.

Könnten Sie mir bitte helfen zu finden, was ich hier falsch gemacht habe?

Answer 1

prüfen dies: https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#substring%28int,%20int%29

Wenn Ihr Datensatz mit 0003 beginnt, record.substring(0,3); wird 000 zurückkehren, nicht 0003. Sie sollten record.substring(0,4); verwenden, um die ID zu bekommen.