java - 编写通用的二分查找方法

Question

我编写了这个二分搜索方法，它返回 ArrayList 中 Book 对象的索引，其中 book id 与输入的 图书编号。

我怎样才能把它变成一个通用方法，将不同类型的 ArrayList 对象和搜索输入作为参数并针对该输入进行搜索？有什么办法可以概括它吗？

 public static int bSearch(ArrayList<Book> a, String input)
    {
        int low = 0;
        int high = a.size() - 1;
        int index = -1;

        while(low <= high)
        {
            int mid = (low + high) / 2;
            if(input.compareTo(a.get(mid).getID()) == 0) //input == target
            {
                //a binary search that returns index of min or max
                index = mid;
                return index;
            }
            else if(input.compareTo(a.get(mid).getID())) < 0) //input < target
                high = mid - 1;
            else if(input.compareTo(a.get(mid).getID()) > 0) //input > target
                low = mid + 1;
        }
        return index;
    }

Answer 1

请注意，您是在重新发明轮子， Collections.binarySearch 中已经实现了通用二分查找。 .

考虑到这一点，为了练习，确保可以通过一些更改来转换您的实现以使其通用:

• 声明类型参数<T>
• 使输入列表的元素具有类型 T而不是 Book (严格来说，? extends T 最理想)
• 指定要搜索的元素类型T
• 添加一个比较器参数，并用它来代替对Book::getID 的比较。

像这样:

public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> comparator) {
    int low = 0;
    int high = list.size() - 1;
    int index = 0;

    while (low <= high) {
        int mid = (low + high) / 2;
        int cmp = comparator.compare(key, list.get(mid));
        if (cmp == 0) {
            index = mid;
            return index;
        } else if (cmp < 0) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return index;
}

当您使用此函数查找 Book 时在按 ID 列出的列表中，您可以将比较器参数写为 Comparator.comparing(Book::getID) . (不用说，列表参数必须已经按书的 id 排序，否则二分查找就没有意义了。)

最后，作为@nic在评论中指出，您的实现有一个非常不受欢迎的行为:当找不到元素时，它返回 0。这不太好，原因有两个:

1. 无法判断该元素是在列表的第一个位置找到，还是没有找到。返回值为 0 时，调用者必须验证列表的第一个元素(如果存在)是否等于搜索到的元素。那是丑陋和痛苦的。

2. 它没有提示缺失的元素在插入后可能适合的位置，这是一条非常有趣的信息。

当列表中没有找到该元素时，通常的做法是返回-1 -index , 其中index是元素应该在的位置，如果它在排序列表中的话。您可以通过更改方法的最后一行来实现:

return -1 - low;

对于您的后续问题，如果您希望此方法将图书 ID 字符串作为要搜索的键，那么第三个参数可以是从图书实例中提取键的函数，而不是比较器。然后，您可以将 key 与从实例中提取的 key 进行比较，而不是通过比较器来比较书籍实例:

public static <T> int binarySearchByStringField(List<? extends T> list, String key, Function<T, String> keyExtractor) {
    int low = 0;
    int high = list.size() - 1;
    int index = 0;

    while (low <= high) {
        int mid = (low + high) / 2;
        int cmp = key.compareTo(keyExtractor.apply(list.get(mid)));
        if (cmp == 0) {
            index = mid;
            return index;
        } else if (cmp < 0) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1 - low;
}