CODEWITHSUNDEEP
javaalgorithmsortingsearch
Jack Twain
Jack Twain

Reputation: 6372

How to represent a bit vector in java so I can search in O(log n)

I have a list of elements and I need to create a signature made of bits for each element. I will end up with a list of bit vectors. After that I need to sort that list of bit vectors lexiographically. After that I need to search for a bit vector in the sorted vectors list.

I found that if I represent the signature as a String, sorting will take O(N) and searching will take O(M logN) using binary search, where M is the length of the string signature.

But I found that with numbers in general, sorting takes O(n LogN) and searching will take O( logN) using binary search.

My question is how to represent the bit vector in java so that I can sort lexicographically and achieves the same performance of dealing with numbers in general?

I'm mostly concerned with achieving that O(logN) search time using binary search, as someone claims to achieve this in a paper but doesn't provide any clue how.

Upvotes: 4

Views: 487

Answers (1)

user949300
user949300

Reputation: 15729

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.

Upvotes: 1

Related Questions