在 Java 中对随机访问文件实施二进制搜索

Question

我正在 Java 中编写一个程序，用户可以在其中使用随机访问文件创建 "databases"（.txt 文件）并在其中存储记录。我正在努力实施二进制搜索，以便为用户提供按 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;
}

这里是 getRecord() 方法，它工作正常，因为即使没有 binarySearch() 方法我也测试过它。

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

问题出在 binarySearch 中使用的 compareTo() 方法。它总是 returns -1，满足 if-else 语句的第二部分。例如，这些是我的一个文件中的记录：

我经历过已婚工资行业
0001 1 无 123.0 kjasdhsjhjh
0002 1 是 123.0 asdhajshjasdhja
0003 1 是 124.0 ajskjkasjd
0004 1 是 124.0 kasjdkjsdjs
0005 1 是 124.0 kajskdjaksdjkas
0006 1 是 123.0 kjksjdkasj

如果我搜索 0001:

高=num_records=5；

低 = 0，因此中 =5/2 = 3

它转到第三条记录并运行 0003 compareTo(0001)。这个比较的结果是-1。因为它小于 0，所以 new Low 等于 Middle + 1 = 3+1 = 4，它去检查第四条记录，即使它不应该。既然是二分查找，那么这里应该是查第二条记录，因为0001小于0003。

你能帮我找出我做错了什么吗？

Answer 1

检查这个：https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#substring%28int,%20int%29

当您的记录以 0003 开头时，record.substring(0,3); 将 return 000，而不是 0003。您应该使用 record.substring(0,4); 来获取 ID。

在 Java 中对随机访问文件实施二进制搜索

Implementing Binary Search on Random Access Files in Java

java

binary-search

compareto

random-access