我有一个元素列表，我需要为每个元素创建一个由位组成的签名。我最终会得到一个位向量列表。之后，我需要按字典顺序对该位向量列表进行排序。之后，我需要在已排序的向量列表中搜索位向量。
我发现如果我将签名表示为字符串，排序将采用 O(N) 并且使用二进制搜索进行搜索将采用 O(M logN)，其中 M 是字符串签名的长度。
但我发现，一般来说，对于数字，排序需要 O(n LogN) 并且使用二进制搜索进行搜索需要 O(logN)。
我的问题是如何在 java 中表示位向量，以便我可以按字典顺序排序并达到与处理数字相同的性能？
我最关心的是使用二分搜索实现 O(logN) 搜索时间，因为有人声称在论文中实现了这一点，但没有提供任何线索。
Expanding on the suggestion by @Keith, use a java.util.BitSet, but extend it to implement Comparable. Implement a lexiographic compare suitable to your domain. Perhaps tweak hashCode() and equals() for speed.
At that point you can easily sort the Collection of BitSets, and use a binary search.
Alternatively, as usual, you could write a Comparator instead to do the lexiographic compare.