二进制搜索未检测到重复项？

Question

我有一组项目、卡片，所有名称都带有字符串名称，所以

Card c1= new card("TheCard")

Card c2= new card("TheOtherCard")

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

所以，

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

//do nothing

else

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 张唯一的卡片，当我检查列表时，它们甚至都不是唯一的 https://i.imgur.com/N9kQtms.png

我已经尝试运行代码未排序，只有 returns 大约 4,000 个结果具有相同的重复卡片问题，当我暴力破解并仅使用基本 .contains 时，可以，但是超级慢

（如果我在我的 post 中搞砸了，我也很抱歉，这是我第一次 post 来这里）

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.

它还声明它 returns:

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.

因此，您的列表应该事先排序，否则它 return 没有任何意义。然后你，它 return 元素的索引或插入点。当心这种技术性。您应该在执行后检查索引处的元素实际上是正确的，而不仅仅是要插入元素的索引 it.

在那里你可以进行这个测试，看看它是否是你的卡：

// 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。

Answer 2

binarySearch 在找到项目时给出一个非负索引。

没有找到时给出插入位置的补码：~index == -index-1

在 a b d e 中搜索 d 得到 2。
在a b e g中搜索d得到~2 == -3，插入位置为2。

所以检查是：

int index = Collections.binarySearch(cards, it, c);
return index >= 0;

此外 Card 应该有一个正确的相等性：

public class Card implements Comparable<Card> {

    ...

    @Override
    public int compareTo(Card other) {
        return name.compareTo(other.name);
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceOf Card)) {
            return false;
        }
        Card other = (Card) obj;
        return name.equals(other.name);
    }

    @Override
    public int hashCode() {
        return name.hashCode();
    }
}

在这种情况下，您可以实现 Comparable<Card> 而不是比较器，因为名称是卡片的读取标识。比较器更适用于按姓氏 + 名字、名字 + 姓氏或城市对人员进行排序。

hashCode 允许使用 HashMap<Card, ...>。

二进制搜索未检测到重复项？

Binary search not detecting duplicates?

java

binary-search