时间戳

首页 > 解决方案 > Java中的数组列表二进制搜索

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

问题描述

我有一个编程任务，需要一个包含方法来覆盖原始数组列表包含方法。该方法应检查列表是否已排序，然后对数组列表执行二进制搜索以查找键。如果 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");
    }
}

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

标签： java

解决方案

正如@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);

推荐阅读