java - 二分查找无法检测重复项？

Question

我有一系列的项目、卡片，全部都有字符串名称，所以

卡 c1= 新卡("TheCard")

卡c2=新卡("TheOtherCard")

然后我使用快速排序对列表进行排序，然后在添加更多卡片之前尝试进行二分搜索以查看卡片是否已经存在

所以，

if(cards.contains(c3)==true)

//什么也不做

其他

cards.add(c3)

我的cards.contains方法是

Comparator<Card> c = new Comparator<Card>() {    
    @Override
    public int compare(Card u1, Card u2) { 
        return u1.getName().compareTo(u2.getName()); 
    } 
};
int index;
index = Collections.binarySearch(cards, it, c);
if (index == -1) {
    return false;
} else {
    return true;
}

但问题是它正在搜索卡片数组，找到不在列表中的卡片并说它们在列表中，并说不在列表中的卡片

我试图添加 10,000 张卡片，其中 8,000 张是唯一的，但 contains 方法返回 2,000 张唯一的卡片，当我检查列表时，它们甚至不是唯一的 /image/olgVb.png

我尝试过运行未排序的代码，并且只返回大约 4,000 个结果，并且存在重复卡片的相同问题，当我强力使用基本 .contains 时，这可以工作，但速度非常慢

(如果我在帖子中搞砸了一些内容，也很抱歉，这是我第一次在这里发帖)

Answer 1

javadoc 声明如下:

Searches the specified list for the specified object using the binary search algorithm. The list must be sorted into ascending order according to the specified comparator (as by the sort(List, Comparator) method), prior to making this call. If it is not sorted, the results are undefined. If the list contains multiple elements equal to the specified object, there is no guarantee which one will be found.

它还声明它返回:

the index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

因此，您的列表应该提前排序，否则它不会返回任何有意义的内容。然后，它确实返回元素的索引或插入点。请注意这种技术性。您应该在执行后检查索引处的元素实际上是否正确，而不仅仅是要插入元素它的索引。

您可以进行此测试，看看它是否是您的卡:

// Test if the card at the index found has got the same name than the card you are actually looking for.
return !index == cards.length && cards[index].getName().equals(it.getName()));

您还可以重写equals以获得更接近的内容:

return !index == cards.length && cards[index].equals(it);

在这两种情况下，如果插入点位于列表末尾，我们都会确保不会出现 ArrayOutOfBoundException。