二分查找实现问题

Question

当我尝试编写以下代码行时：

int foundIndex = Collections.<K>binarySearch(keys, key);

出现了错误：类型为Collections的参数化方法<K>binarySearch(List<? extends Comparable<? super K>>, K)不适用于参数(List<K>, K)

以上错误是什么意思，我的代码哪里出了问题？

    // Comparator used to sort elements; may be null if elements are Comparable
    public final Comparator<K> cmp;  


    {
        super(new ArrayList<K>(), new ArrayList<V>());
        cmp = new MyComparator<K>();
    }

    // Use the given comparator to sort the keys

        //super(new ArrayList<K>(), new ArrayList<V>());
        this.cmp = cmp;
    }


    {
        if(!(key instanceof Comparable) && cmp == null)
            throw new RuntimeException("The key is not instance of Comparable or comparator object is null");
    }

    public int indexOf(K key) 
    {
        int foundIndex = Collections.<K>binarySearch(keys, key);

        return foundIndex;
    }

    public int compareTo(K otherKey) 
    {
        int result = 0;
        for(int i = 0; i < keys.size(); i++)
        {
            result = ((Comparable<K>) keys.get(i)).compareTo(otherKey);
        }
        return result;
    }

MyComparator类

import java.util.Comparator;



    @Override
    public int compare(K key1, K key2)
    {
        return -1;
    }

}

- user4833678

---

“keys” 声明在哪里？ - Eran

Answer 1

你的问题是FastGetListMM<K, V>实现了Comparable<K>，但是Collections.<K>binarySearch(list, value)期望一个列表是Comparable<K>类型。

应该让K实现Comparable<K>，而不是FastGetListMM。如果你想使用Collections.<K>binarySearch(keys, key)，则需要让FastGetListMM实现List<Comparable<K>>，而不是Comparable<K> - 并确保FastGetListMM中的所有项目按升序排列。

- Raniz

Answer 2

要使用二分查找的实现，您需要实现可比较的 K，还有另一个函数接收可比较对象本身。在您的情况下，您需要调用 Collections.<K>binarySearch(keys, key, new MyComparator());

- Benjy Kessler