代码之家 › 专栏 › 技术社区 › Jason

为什么比较器在应该为假时返回真?

string-comparison data-structures java

Jason · 技术社区 · 14 年前

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

//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++ 这足以通过结构测试,但却一个接一个地偏离了预期的起点。

那么,当这显然是错误的时候,为什么它会返回真的呢?

编辑添加了子列表方法的打印输出,预期从I到O运行

输入测试字符串= abcdefghijklmnopqrstuvwxyzaeiou 从子列表返回方法:
第1块(使用了第4块,共10块):[H][I][I][J]
区块2(使用4/10):[K][L][M][N]

H不应该出现在列表中,但是 comp.compare(node.items[index], item)==0 返回正确的i==h,这显然是错误的。

编辑两个 项目的第二部分要求我们解析文本文件,从艺术家、标题和歌词字段构建歌曲对象,然后使用前缀对标题进行搜索。这里发生的错误不会出现在单字母和多字母搜索中,所以我认为问题在于测试中的StringCMP嵌套类。

5 回复 | 直到 14 年前

Luke Hutteman 14 年前

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

当前的方法引入了不必要的复杂性,如果输入数组包含所有相同的值,则可能会将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;

Jonathan 14 年前

你知道吗 compare() 应该回来吗?通常这样的函数如果第一个参数小于第二个参数,则返回负值;如果相等,则返回0;如果第一个参数大于第二个参数,则返回正值。

另外,在数组上执行排序的是什么?你能把你的 binarySearch() 代码,这样我们就能知道问题是否在那里?

Luke Hutteman 14 年前

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

Dima 14 年前

检查 official description 比较(字符串)方法的

从文件:

返回:如果参数字符串等于此字符串,则返回值0;如果此字符串在词典上小于字符串参数,则返回值小于0;如果此字符串在词典上大于字符串参数,则返回值大于0。

Powerlord 14 年前

出于好奇,这难道不是更符合你想要做的吗?

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