1

课堂项目让我们阅读包含在单个文本文件中的 10,514 首歌曲的标题、艺术家和歌词。项目的当前部分让我们编写一个有序展开的链表并在标题字段上运行搜索。还编写了比较器以按标题对列表进行排序。我们必须跟踪找到匹配项所需的比较

测试时，我得到了一些奇怪的结果。例如，运行
angel搜索返回 23 个匹配项并需要 552 次比较，它与教授给出的答案匹配

t返回零个匹配项并需要 9530 次比较，其中预期 1148 个匹配项
ta返回 62 个匹配项并需要 8455 次比较

s返回无匹配项并且需要 8383 次比较
sa返回 89 次匹配并且需要 7355 次比较

我的搜索算法运行如下：

  1. 遍历列表以找到第一个匹配项
  2. 遍历列表以查找与搜索字段不匹配的第一个实例
  3. 将开始和结束对象发送到数据结构的 Sublist 方法，该方法遍历这两个对象并构建一个单独的匹配列表
  4. 返回匹配列表

对于第一步和第二步，我通过以下方式将当前值与搜索值进行比较
if (currentSong.getTitle().toLowerCase().startsWith(titleSearch))

这行代码通过单个字母搜索返回 false，但是当添加 a 时，找到值是什么？最好，我想要一个不需要我在调试器中手动单步执行循环的 8000 多次迭代的解决方案。此外，教授用预期值对结构进行了测试，我的代码通过了所有测试。

4

1 回答 1

1

我发现了问题所在。在 subList 方法中，我使用了二分查找方法来识别第一个找到的匹配项的索引位置。然而，由于二分搜索只返回它遇到的第一个匹配，我有一个循环向后遍历数组以找到真正的第一个匹配。

但是，在这种情况下，从二分搜索返回的第一个命中是在 0 索引处，所以当我向后走时，抛出了 ArrayIndexOutOfBoundsException，从而使整个事情短路。添加第二个测试解决了这个问题。

于 2010-10-28T00:37:08.953 回答