我的二进制搜索算法有问题吗？

Question

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

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

下面是 class 我的搜索算法：

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

这是我的排序算法： public class 排序 { 静态私有字符串 strTemp；静态私有 int i； static private 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 class:

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

并且不要忘记按照之前 post

中所述对您的列表进行排序

Answer 2

问题出在您搜索的最后一步。您有机会更新 'first' 和 'last'，并在下一次迭代中找到该值，但您却从循环中跳出。

解决方案：完全删除变量 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 开始并包括 first，但不包括 last） .

但是，在您的循环中，您设置了 last = middle - 1，如果您的搜索范围是闭区间 [first, last]（从 first 到 last).

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

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

我的二进制搜索算法有问题吗？

Is there something wrong with my binary search algorithm?

java

arraylist

binary-search