为什么compareTo 在应该为 false 的时候却返回 true ？

Question

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

//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++ 进行补偿，这足以通过结构测试，但与预期的起点相差一分。

那么为什么当它明显是 false 时却返回 true 呢？

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

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

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

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

Answer 1

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

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

Answer 2

当您减少每场比赛的索引时，您的 while 循环

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

会超出第一个匹配项，从而使您的索引不再匹配。相反，对索引 1 处的项目调用比较器可以解决此问题：

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

Answer 3

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

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

Answer 4

查看官方说明compareTo(String) 方法的

来自文档：

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

Answer 5

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

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