Java 中的数组列表二进制搜索

Question

我有一个编程作业，需要一个覆盖原始arrraylist包含方法的包含方法。该方法应检查列表是否已排序，然后在数组列表中执行二进制搜索以查找键。如果数组列表没有排序，那么它应该只从数组列表执行原始包含方法。这是我现在的代码。

public void contains(String key) {
System.out.println("Initializing");
if(isSorted()) {
int first = 0;
int last = this.size() - 1;
while(last >= first) {
int mid = (first + last) / 2;
if (this.get(mid).equals(key)) {
System.out.println(this.get(mid));
}
if (this.get(mid).compareTo(key) == 1) {
System.out.println(this.get(mid));
first = mid + 1;
}
if (this.get(mid).compareTo(key) == -1) {
System.out.println(this.get(mid));
last = mid - 1;
}
}
}
else {
System.out.println("Character does not exist");
}
}

当我运行它时，我没有收到任何错误，但是当我尝试执行搜索时没有任何反应。

Answer 1

正如@John Bollinger在评论中所说。您的方法不会重写contains()方法，因此根本不会调用该方法的实现。

您的方法应与定义List接口contains()方法的签名匹配，因此这实际上是覆盖ArrayList类的实现。

所以你的方法应该是这样的：

public class MyList extends ArrayList<String> {
@Override
public boolean contains(Object o) {
// your logic goes here
}
}

还要记住，如果你的数组没有排序，你的方法什么都不做，这不是你描述的问题应该做的事情。若要在ArrayList中使用contains方法的默认实现，可以编写：

if (sorted)
// do binary search
else
return super.contains(key);