如何实现数组列表二进制搜索Java?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (1)
  • 关注 (0)
  • 查看 (126)

有一个编程任务,需要一个覆盖原始arrraylist contains方法的contains方法。该方法应检查列表是否已排序,然后对arraylist执行二进制搜索。如果arraylist没有排序,那么它应该只是从arraylist中预先形成原始的contains方法。这是我现在的代码

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");
    }
}

运行时没有错误,但是当我尝试预先形成搜索时没有任何反应

提问于
用户回答回答于

正如@John Bollinger在评论中所述,方法不会覆盖该contains()方法,因此根本不会调用该方法的实现。方法应该匹配contains()定义List接口的方法的签名,这样实际上是覆盖了ArrayList类的实现。

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

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

还要记住,如果你的数组没有排序,你的方法什么也不做,这不是你描述问题时应该做的。要使用该contains方法的默认实现,ArrayList可以编写:

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

扫码关注云+社区

领取腾讯云代金券