java - 如何使用二进制搜索从已排序的 TreeSet 中检索元素？

Question

我正在尝试将多个排序列表合并到一个 TreeSet 中。然后我想在该 TreeSet 上应用二进制搜索算法以 O(log n) 时间复杂度检索元素。

下面是我的代码，我在其中一个方法中传递列表列表并将它们组合到 TreeSet 中以避免重复... inputs 中的所有列表> 已排序 -

private TreeSet<Integer> tree = new TreeSet<Integer>();

public void mergeMultipleLists(final List<List<Integer>> inputs) {
    tree = new TreeSet<Integer>();
    for (List<Integer> input : inputs) {
        for(Integer ii : input) {
            tree.add(ii);
        }
    }
}

public List<Integer> getItem(final Integer x) {
    // extract elements from TreeSet in O(log n)
}

• 首先，这种将多个排序列表合并到 TreeSet 中的方法是否正确？有什么直接的方法可以有效地合并 TreeSet 中的多个排序列表？
• 其次，我如何以 O(log n) 的时间复杂度从 TreeSet 中提取一个元素？我想在 TreeSet 中找到一个元素 x，如果它存在，则返回它，如果不存在，则返回 中的下一个最大值>树集。

或者与我目前使用的数据结构相比，我可能更适合另一种数据结构？

更新代码:-

private TreeSet tree = new TreeSet();

public SearchItem(final List<List<Integer>> inputs) {
    tree = new TreeSet<Integer>();
    for (List<Integer> input : inputs) {
        tree.addAll(input);
    }
}

public Integer getItem(final Integer x) {
    if(tree.contains(x)) {
        return x;
    } else {
        // now how do I extract next largest 
         // element from it if x is not present
    }
}

Answer 1

TreeSet 由 NavigableMap 支持，特别是 TreeMap。在 TreeSet 上调用 contains() 委托(delegate)给 TreeMap.containsKey()，这是一个二进制搜索实现。

您可以使用 TreeSet.contains() 检查对象是否包含在集合中，但您必须首先拥有该对象。如果您希望能够查找和检索对象，那么 Map 实现会更好。