java 使用二分搜索从 TreeSet 返回一个元素

Returning an element from a TreeSet using binary search

提问by exent

In TreeSet there is a method called contains that returns true if an element is in the set. I assume that this method uses binary search and does not iterate through all the elements in ascending order. Am I right?

在 TreeSet 中有一个称为 contains 的方法，如果元素在集合中，则返回 true。我假设此方法使用二分搜索并且不会按升序遍历所有元素。我对吗？

I have a TreeSet that contains objects of a class that uses two String instance variables to distinguish it from other objects of the same class. I want to be able to create a method that searches the TreeSet by comparing the objects two instance variables (using get methods of course) with two other String variables and if they are equal, return the element. If the instance variables are less than go to the first element in the right subtree or if they are greater search in the left subtree etc. Is there a way to do this?

我有一个 TreeSet ，它包含一个类的对象，该类使用两个 String 实例变量将其与同一类的其他对象区分开来。我希望能够通过将对象的两个实例变量（当然使用 get 方法）与其他两个 String 变量进行比较来创建一个搜索 TreeSet 的方法，如果它们相等，则返回该元素。如果实例变量小于转到右子树中的第一个元素，或者如果它们在左子树中更大搜索等。有没有办法做到这一点？

I know I could just store the objects in an ArrayList and use binary search to find the object, but this wouldn't be as fast as just searching the TreeSet.

我知道我可以将对象存储在 ArrayList 中并使用二进制搜索来查找对象，但这不会像搜索 TreeSet 那样快。

采纳答案by ColinD

Rather than using a TreeSet, you could store your objects in a TreeMap<Foo, Foo>or TreeMap<FooKey, Foo>(if you can't easily create a new actual Fooeach time you want to search). Sets are not really intended for lookup.

TreeSet您可以将对象存储在TreeMap<Foo, Foo>or 中，而不是使用，TreeMap<FooKey, Foo>（如果您不能在Foo每次要搜索时轻松创建新的实际值）。Sets 并不是真正用于查找。

For the FooKeyexample, FooKeywould be a simple immutable class that just contains the two Strings and is Comparable. Finding the value of Foofor two Strings would then be a simple matter of treeMap.get(new FooKey(firstString, secondString)). This does of course use the tree traversal you want to find the value.

对于FooKey例如，FooKey将只包含两个简单的不可变类StringS和是Comparable。找到Foo两个Strings的值将是一个简单的问题treeMap.get(new FooKey(firstString, secondString))。这当然会使用您要查找值的树遍历。

回答by greg

set.tailSet(obj).first();

does what you want.

做你想做的。

回答by Konstantin Komissarchik

You should either implement Comparable on your object or create a separate Comparator class that you pass in at the time TreeSet is constructed. This allows you to interject your custom entry comparison logic and let the TreeSet do its optimized store/search thing.

您应该在对象上实现 Comparable 或创建一个单独的 Comparator 类，在构建 TreeSet 时传入该类。这允许您插入自定义条目比较逻辑，并让 TreeSet 执行其优化的存储/搜索操作。

回答by Justin Waugh

One thing I was wondering is why you want to search into a sorted set? If you want to be able to iterate in order as well as lookup quickly you may benefit from storing your objects in two separate data structures. One like your SortedSet<Foo>and then also a HashMap<FooKey,Foo>similar to what ColinD mentioned. Then you get constant time lookups instead of log(n) on the TreeMap. You have a write penalty of having to write to both structures, and a memory resource penalty of having the two data structures, but you have fully optimized your access to the data.

我想知道的一件事是为什么要搜索已排序的集合？如果您希望能够按顺序迭代并快速查找，您可能会受益于将对象存储在两个单独的数据结构中。一个喜欢你的SortedSet<Foo>，然后也HashMap<FooKey,Foo>类似于 ColinD 提到的。然后，您将在 TreeMap 上获得恒定时间查找而不是 log(n)。必须同时写入两个结构会导致写入损失，并且拥有两个数据结构会导致内存资源损失，但是您已经完全优化了对数据的访问。

Also if memory resources are constrained, and your strings are really what differentiate the objects, then you can just implement hashcode()and equals()on your object Fooand then just use them as both the key and value (like HashMap<Foo,Foo>. The caveat there is that you have to construct a Footo call the getter.

此外，如果内存资源的限制，你的字符串是真的什么区分对象，那么你可以实现hashcode()和equals()你的对象Foo，然后只用它们作为键和值都（像HashMap<Foo,Foo>。需要说明的还有，你必须建立一个Foo调用吸气剂。

回答by Justin Waugh

You got the answer about using comparable/comparator, but I thought I would add that you are right that contains() does a binary search, though you shouldn't need to know those details

你得到了关于使用可比较/比较器的答案，但我想我会补充说你是对的， contains() 进行二分搜索，尽管你不需要知道这些细节