1

我正在调试来自我的数据结构类项目的错误搜索返回。当前的这个项目要求我们构建一个有序展开链表，并对内容进行搜索，然后返回从包含起点到排他终点的项目子列表。为此，我必须搜索内部数组以找到起始元素的索引点。我通过二分搜索来做到这一点，但由于这只返回第一个找到的匹配并且在它之前可能还有其他匹配，所以我必须在数组中返回以找到第一个真正的匹配。我这样做是通过

//get first index match, work backwards
int index= binarySearch(node.items, 0, node.numUsed, item, comp);
while (index>0 && comp.compare(node.items[index], item)==0){
    index--;
}

教授提供了测试代码，它分解了一个字符串并将每个字符作为一个项目添加到结构中。他还包括一个嵌套的 StringCmp 类，它在上面的二分搜索声明中被引用comp。他的比较方法是

public int compare(String s1, String s2) {
  cmpCnt++;
  return s1.compareTo(s2);
}

但是，当对从 i 到 o 的子列表方法运行测试时，此方法在何时返回一个真值comp.compare(h,i)==0，这会从我编写的搜索类中抛出我的开始结果。我最初的补偿return index++足以通过结构测试，但将预期的起点偏离了一个。

那么，当它显然是错误的时候，为什么它会返回 true 呢？

编辑添加了子列表方法的打印输出，预计从 i 运行到 o

输入测试字符串 =abcdefghijklmnopqrstuvwxyzaeiou 从子列表方法返回：
块 1（使用 4 of 10）：[h][i][i][j]
块 2（使用 4 of 10）：[k][l][m][n ]

h 根本不应该在列表中，但是comp.compare(node.items[index], item)==0i == h 返回 true，这显然是错误的。

编辑二 项目的第二部分要求我们解析一个文本文件，从 Artist、Title 和 Lyrics 字段构建 Song 对象，然后使用前缀对标题进行搜索。这里发生的错误不会出现在单字母和多字母搜索中，所以我认为问题出在测试中的 StringCmp 嵌套类。

4

5 回答 5

5

你知道compare()应该返回什么吗？一般来说，如果第一个参数小于第二个参数，则返回负值，如果它们相等，则返回 0，如果第一个参数大于第二个参数，则返回正值。

另外，什么在你的数组上执行排序？您能否发布您的binarySearch()代码，以便我们查看问题是否存在？

于 2010-10-29T13:19:12.430 回答
2

你的while循环

while (index>0 && comp.compare(node.items[index], item)==0){
    index--;
}

当您为每个匹配减少索引时，将第一个匹配超过一个，使您处于不再匹配的索引。在 index-1 的项目上调用 Comparator 可以解决这个问题：

while (index>0 && comp.compare(node.items[index-1], item)==0){
    index--;
}
于 2010-10-29T17:56:29.133 回答
1

由于您实现了自己的二进制搜索，因此您应该继续使用它来搜索数组中的第一个匹配元素，而不是在找到匹配项后立即停止。

您当前的方法引入了不必要的复杂性，并且如果您的输入数组包含所有相同的值，则可能会将 O(log N) 算法更改为 O(N) 算法。

我假设您当前的算法看起来像

int low = 0; 
int high = a.length-1;
while (low <= high) {
    int mid = (low + high) / 2;
    int cmp = comp.compare(a[mid], key);
    if (cmp < 0)
        low = mid + 1;
    else if (cmp > 0)
        high = mid - 1;
    else
        return mid;
}
return -1;

用下面的代码替换它应该可以解决问题

int low = 0;
int high = a.length-1;
while (low < high) {
    int mid = (low + high) / 2;
    int cmp = comp.compare(a[mid], key);
    if (cmp < 0)
        low = mid + 1;
    else
        high = mid;
}
if (comp.compare(a[low], key) == 0)
    return low;
else 
    return -1;
于 2010-10-29T15:12:28.070 回答
0

查看compareTo(String) 方法的官方描述

从文档：

返回： 如果参数字符串等于该字符串，则值为 0；如果此字符串按字典顺序小于字符串参数，则值小于 0；如果此字符串按字典顺序大于字符串参数，则值大于 0。

于 2010-10-29T13:35:25.713 回答
0

出于好奇，这不是更符合您想要做的事情吗？

//get first index match, work backwards
int index= binarySearch(node.items, 0, node.numUsed, item, comp);

for (int i = index; i >= 0; i--) {
    if (comp.compare(node.items[index], item)==0))
        index = i;
}
于 2010-10-29T13:53:47.520 回答