java - 使用泛型 Java 对数组/比较器进行二分搜索

Question

我正在努力使一个用于二分搜索的比较器在对象数组上工作。本质上，目标是搜索不规则数组以找到项目的第一个匹配项或最接近的匹配项以提供插入点。该方法传入一个泛型(这是不可更改的 - 因为这是家庭作业)，但您无法创建泛型类型的数组...因此，我的比较器抛出错误:“数组类型中的方法二元搜索(对象[]，对象)不适用于参数(对象[]，E，比较器)”。也许我需要转换通用元素“item”？我不知道。代码:

private Location findFirst(E item) {
    Location current;
    int closestMatchArray1;
    int closestMatchArray2;

Object[] firstItemInArray2 = new Object[numArrayInUse];
Object firstItem;

Comparator<E> comparator = new CompareElement();

for (int i - 0; i < numArrayInUse; i++) {
    firstItem = topArray[i];
    firstItemInArray2[i] = firstItem;
}

closestMatchArray1 = Arrays.binarySearch(firstItemInArray2, item, comparator);

次要但相关的问题。在比较器中，我尝试调用 Comparable 方法“compareTo”来获取一个负整数，该负整数给出了搜索失败时某个项目在数组中的大致位置，但同样，我在泛型方面遇到了麻烦，收到此错误:“方法compareTo(E) 对于类型 E 是未定义的”。代码:

public class CompareElement implements Comparator<E> {
  public int compare(E firstItem, E secondItem) {
     return firstItem.compareTo(secondItem);
  }
}

Answer 1

我认为您要么需要 Comparator<Object>或者你需要一个 E[] 的数组。对于后者，我建议查看这两篇文章:

• How to create a generic array in Java?
• Object array not getting cast to a generic type

鼓励阅读以上内容。

<小时/>

选项 1:Array.newInstance()

假设 item 永远不为 null

根据我在上述帖子中读到的内容，如果您知道 item 永远不会是 null ，你可以尝试这样的事情......

@SuppressWarnings("unchecked")
private Location findFirst(E item) {
    Location current;
    int closestMatchArray1;
    int closestMatchArray2;

    // Object[] firstItemInArray2 = new Object[numArrayInUse];
    // Object firstItem;

    E[] firstItemInArray2 
            = (E[]) Array.newInstance(item.getClass(), numArrayInUse); 
    E firstItem;

    Comparator<E> comparator = new CompareElement();

    for (int i = 0; i < numArrayInUse; i++) {
        firstItem = (E) topArray[i];
        firstItemInArray2[i] = firstItem;
    }

    closestMatchArray1 = Arrays.binarySearch(firstItemInArray2, item, comparator);

<小时/>

选项2:Array.newInstance()

需要类参数

如果您不能保证该商品永远不会 null ，并且您无法为 null 提供任何特殊处理值，您可以强制 Class<?>传入的参数，如下...

@SuppressWarnings("unchecked")
private Location findFirst(E item, Class<E> clazz) {
    Location current;
    int closestMatchArray1;
    int closestMatchArray2;

    // Object[] firstItemInArray2 = new Object[numArrayInUse];
    // Object firstItem;

    E[] firstItemInArray2 
            = (E[]) Array.newInstance(clazz, numArrayInUse); 
    E firstItem;

    Comparator<E> comparator = new CompareElement();

    for (int i = 0; i < numArrayInUse; i++) {
        firstItem = (E) topArray[i];
        firstItemInArray2[i] = firstItem;
    }

    closestMatchArray1 = Arrays.binarySearch(firstItemInArray2, item, comparator);

<小时/>

选项 3:对象比较器包装

丑陋，但有效

或者，您可以创建 Comparator<Object>包装您现有的Comparator<E> ，如下(我认为这有点黑客，但它对我来说始终有效)...

    private Location findFirst(E item) {
    Location current;
    int closestMatchArray1;
    int closestMatchArray2;

    Object[] firstItemInArray2 = new Object[numArrayInUse];
    Object firstItem;

    // Comparator<E> comparator = new CompareElement();
    Comparator<Object> comparator = new Comparator<Object>() {
        private final Comparator<E> delegate = new CompareElement();

        @Override
        @SuppressWarnings("unchecked")
        public int compare(Object o1, Object o2) {
            return delegate.compare((E) o1, (E) o2);
        }
    };

    for (int i = 0; i < numArrayInUse; i++) {
        firstItem = topArray[i];
        firstItemInArray2[i] = firstItem;
    }

    closestMatchArray1 = Arrays.binarySearch(firstItemInArray2, item, comparator);

<小时/>

希望这有帮助!