我编写了这个二进制搜索方法,它返回BookArrayList对象的索引,其中book id与输入的book id匹配。
如何将其转换为一个泛型方法,该方法以不同类型的对象和搜索输入作为参数并对该输入进行搜索?我有办法概括一下吗?

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

最佳答案

请注意,您正在重新发明轮子,一个通用的二进制搜索已经在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;
}

使用此函数在按ID列出的列表中查找Book时,可以将比较器参数编写为Comparator.comparing(Book::getID)
(不用说,list参数必须已经按book id排序,否则二进制搜索就没有意义。)
最后,正如@nic在注释中指出的,您的实现有一个非常不受欢迎的行为:当找不到元素时,它返回0。这不太好,有两个原因:
无法判断元素是在列表的第一个位置找到的,还是没有找到。在返回值为0时,调用方必须验证列表的第一个元素(如果存在)是否等于搜索的元素。那既丑陋又痛苦。
如果插入了缺少的元素,它不会提示该元素可以放在什么位置,这是一条非常有趣的信息。
当在列表中找不到元素时,通常的做法是返回-1 -index,其中index是元素在已排序列表中应位于的位置。您可以通过更改方法的最后一行来实现这一点:
return -1 - low;

对于后续问题,如果希望此方法将book id字符串作为要搜索的键,则第三个参数可以是从book实例中提取键的函数,而不是比较器然后,您可以将键与从实例中提取的键进行比较,而不是通过比较器比较书本实例:
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;
}

08-06 01:16
查看更多