二进制搜索帮助:读取文件到数组，找到一个特定的行

Question

在文件中，每个条目将包含两行;第一行是号码，第二行是标题。文件中的条目将按数字升序排列。

创建一个程序，将a文件读入数组。然后，用户将根据数字请求标题。您的程序将执行二进制搜索来查找标题。

当前，我从文件中读取所有内容到arrayList中，然后从那里将其转换为数组。

我的第一个主要问题是，我的二进制搜索方法似乎不工作;我尝试搜索一个数字，结果返回false。其次，即使这成功了，我也不确定如何记录文本文件中的哪一行找到了结果。我认为这是必要的，因为我必须输出后面的行。这是文本文件的一个示例。

2

弥赛亚剧

4

晚祷7

善人在迫害下的祈祷

等。这是我当前的代码

package Psalms;
import java.io.*;
import javax.swing.*;
import java.util.ArrayList;
import java.util.List;
public class Psalms {

public static void main(String[] args) throws IOException {
    // Creates array list. Reads lines into it
    List<String> psalms = new ArrayList<String>();
    BufferedReader readFile = new BufferedReader(new FileReader("Psalms.txt"));
    String line;
    while ((line = readFile.readLine()) != null) {
        psalms.add(line);
    }
   readFile.close();
    String[] psalmArray = new String[psalms.size()];
    psalmArray = psalms.toArray(psalmArray);
    //Asks user what to search for.
    String psalmSearch = (JOptionPane.showInputDialog("What number Psalm would you like to search for?"));
    System.out.println("Binary Search: " + psalmSearch + " " + binarySearch(
            psalmArray, 0, psalmArray.length - 1, psalmSearch));
}
public static boolean binarySearch(String myArray[], int left,
        int right, String searchForPsalm) {
    int middle;
    if (left > right) {
        return false;
    }
    middle = (left + right) / 2;
    if (myArray[middle].equals(searchForPsalm)) {
        return true;
    }
    if (searchForPsalm.compareTo(myArray[middle]) < 0) {
        return binarySearch(myArray, left, middle - 1,
                searchForPsalm);
    } else {
        return binarySearch(myArray, middle + 1, right,
                searchForPsalm);
    }
}

}

Answer 1

假设您的文件被正确验证(即每个诗篇编号后跟一个文本行)，那么对于现有的binarySearch方法，需要进行2个更正:

    .
    .
    middle = (left + right) / 2;
    middle += middle & 1;  // to the nearest even number
    .
    .
    .
    } else {
        return binarySearch(myArray, middle + 2, right,
                searchForPsalm);
    }
}

1)由于所有的诗篇都在偶数数组位置，您需要确保将中间设置为最接近的偶数偏移。

2)对于'right side'分区，您应该通过将其设置为'middle + 2'来跳过文本行。

这将确保您按预期比较诗篇的数字。

现在不是返回一个布尔值，而是返回字符串来显示找到的相关文本，下面是修改后的方法:

public static String  binarySearch(String myArray[], int left,
        int right, String searchForPsalm) {
    int middle;
    if (left > right) {
        return "";
    }
    middle = (left + right) / 2;
    middle += middle & 1;
    if (myArray[middle].equals(searchForPsalm)) {
        return myArray[middle + 1];
    }
    if (searchForPsalm.compareTo(myArray[middle]) < 0) {
        return binarySearch(myArray, left, middle - 1,
                searchForPsalm);
    } else {
        return binarySearch(myArray, middle + 2, right,
                searchForPsalm);
    }
}

如果没有找到条目，它将返回一个空字符串。

另外，如果你需要'middle'值也被返回，你可以修改它来返回一个对象，比如Result，它同时具有'middle'和字符串值——参见下面的例子:

如何在java中返回多个值?

Answer 2

现在，您正在做的是将文件中的每行一个String添加到List中。因此，这个列表看起来像这样:

<"2", "The messianic drama", "4", "Evening prayer", "7">

问题是，当你试图对这个执行二进制搜索时，你正在比较一些带有标题的字符串，和一些带有数字的字符串。

以下是我推荐的方法，假设您得到的文件已经排序:

当您读取文件的行时，交替将它们添加到两个不同的列表中，其中一个包含标题，另一个包含整数形式的数字。当您从文件中添加数字时，请确保使用integer . parseint (String)将其转换为整数。我们的想法是像这样创建两个列表:

Title List = <"The messianic drama", "evening prayer", "Prayer of the virtuous under 
persecution">
Tile Number List: <2,4,7>

你看到2和The messianic drama在另一个列表中的索引是一样的吗?

然后，当您执行二进制搜索寻找标题编号时，如果您找到了您正在寻找的数字，则只需返回标题列表中相同位置的字符串。

如果你的标题在文件中没有按顺序编号，你可能要考虑制作一个由String和Integer组成的Tuple。这有点复杂，因为您必须创建一个类并实现一个Comparator，以便对它们进行正确排序。