我的二叉搜索算法有问题吗?

Question

我正在编写一个程序，您可以在其中输入将存储在ArrayList中的单词。然后，您可以通过在文本字段中输入这些单词并按按钮来搜索这些单词。(如果按下另一个按钮，您也可以对它们进行排序(。如果找到该单词，则应打印出该单词的 ArrayList 中的位置，如果未找到，则应打印出来。我认为这一直有效，直到最近我测试它时(它以前工作过(：我输入了一个我知道在 ArrayList 中的单词，它使它打印出该单词在 ArrayList 中的位置(这就是我希望它做的事情(。然后我输入了一个我知道在 ArrayList 中不存在的单词，这使得它打印出该单词不存在(这也是我希望它做的(。但是当我在那之后搜索一个我知道存在于 ArrayList 中的单词时，它打印出找不到该单词。然后，我用另一个我知道存在于 ArrayList 中的词来尝试这个，但我也找不到。在此之后，我已经重新启动了该程序几次，有时它有效，有时它不起作用，我不知道为什么或为什么不......

在我运行算法之前，数组被排序，所以我知道这不是问题......

下面是我的搜索算法的类：

public class SearchAlg {
  public static String binary (ArrayList<String> list, String user) {
    int first = 0;
    int found = 0;
    int middle = 0;
    int last = list.size();
    String strFound = "";
    while (first < last && found == 0) {
        middle = ((first + last) / 2);
        if (user.compareTo(list.get(middle)) > 0) {
            first = middle + 1;
        } else if (user.compareTo(list.get(middle)) == 0) {
            found = 1;
        } else if (user.compareTo(list.get(middle)) < 0) {
            last = middle - 1;
        }
    }
    if (found == 1) {
        strFound = "The word " + user + " exists on the place " + middle + " in the Arraylist";
    } else {
        strFound = "The word " + user + " does not exist in the Arraylist";
    }
    return strFound;
  }
}

这是我的排序算法： 公共类排序 { 静态私有字符串 strTemp; 静态私有 int i; 静态私有 int n;

public static ArrayList bubbelSort (ArrayList<String> list) {
    for (i = 0; i < list.size(); i++) {
        for (n = 0; n < list.size() - i - 1; n++) {
        if (list.get(n).compareTo(list.get(n + 1)) > 0) {
            strTemp = list.get(n);
            list.set(n, list.get(n + 1));
            list.set(n + 1, strTemp);
        }
    }
    }
    return list;
}

这是我Main课：

ArrayList<String> list = new ArrayList();
private void btnEnterActionPerformed(java.awt.event.ActionEvent evt) {                                          
    txtaOutput.setText("");
    String wrd = txtfEnter.getText();
    list.add(wrd);
    for (int i = 0; i < list.size(); i++) {
        txtaOutput.append(list.get(i) + "n");
    }
}
private void btnSortActionPerformed(java.awt.event.ActionEvent evt) {                                            
    txtaOutput.setText("");
    Sort.bubbelSort(list);
}
private void btnSearchActionPerformed(java.awt.event.ActionEvent evt) {                                        
    // TODO add your handling code here:
    String user = txtfSearch.getText();
    txtaOutput.setText("");
    String bin = SearchAlg.binary(list, user);
    txtaOutput.append(bin);
}

我不知道是什么原因造成的，所以任何帮助不胜感激！

编辑：我现在知道问题是ArrayList中的第一个项目不可搜索。因此，例如，如果 ArrayList 由 a, b, c 组成，则只有 b 和c是可搜索的。如果我尝试搜索a，它说找不到它。

Answer 1

    int first= 0;
    int last= a.length - 1;
    while (first<= last) {
        int middle = first+ (last- first) / 2;
        if      (user.compareTo(list.get(middle)) < 0) last = middle - 1;
        else if (user.compareTo(list.get(middle)) > 0) first= middle + 1;
        else {
        found =1 ;
        break;
        }
    }

并且不要忘记按照上一篇文章中提到的对列表进行排序

Answer 2

问题出在搜索的最后一步。您有可能更新"第一个"和"最后一个"，在下一次迭代中，您会找到该值，但相反，您会中断循环。

解决方案：完全删除变量found，以及以下两行：

} else if (user.compareTo(list.get(middle)) == 0) {
        found = 1;

以及你现在写的地方...

if (found == 1) {    

。而是做...

if (user.compareTo(list.get(first)) == 0) {

Answer 3

你差了一个。

你用last = list.size()初始化方法，这意味着你正在搜索半开区间[first, last>(从并包括first，到但不包括last(。

但是，在您的循环中，您设置了 last = middle - 1 ，如果您的搜索范围是闭合间隔[first, last](从并包括first，到并包括last(，这将起作用。

您应该决定last应该指向最后一个元素还是指向最后一个元素之后。如果你选择后者，这是你的循环：

while (first < last && found == 0) {
    middle = ((first + last) / 2);
    if (user.compareTo(list.get(middle)) > 0) {
        first = middle + 1;
    } else if (user.compareTo(list.get(middle)) == 0) {
        found = 1;
    } else if (user.compareTo(list.get(middle)) < 0) {
        last = middle;                                   // <-- Remove -1
    }
}