有没有一种聪明的方法可以在 O(logn) 中实现相当于 C# SortedDictionary 中的 Java TreeMap 的 CeilingEntry？

Question

您可能会看到有关此主题的类似问题 - 比如这个 one 和 this。

我想使用 SortedDictionary 的主要原因是在 O(log n) 中具有搜索和插入功能 - 平衡二叉搜索树的最佳情况复杂度。我感兴趣的搜索用例是当找不到要搜索的键时，即当我们想要查找大于或小于搜索到的项目时（如 Java 中的

CeilingEntry

和

FloorEntry

） - 它应该可以在

O(log n)

，因为底层数据结构允许这样做。

前面的答案建议使用某种形式的

SortedDictionary<TKey,TValue>.Keys

，但问题是我们无法在

SortedDictionary<TKey,TValue>.KeyCollection

类上执行内置的BinarySearch。为此提出的解决方法是将键转换为列表，然后使用 BinarySearch 并查找 apt 索引，但转换为列表将达不到目的，因为它是一个

O(n)

操作。

我有一个想法，使用KeyCollection类的GetEnumerator直接对其进行二分查找，但我认为它非常难看。

Answer 1

此答案中的代码已使用 .NET 8 进行了测试。由于缺少

IMinMaxValue<TSelf>

（以及一般的接口静态），因此需要进行调整才能与 .NET 6 或 .NET Framework 一起使用。

您想要的行为可以通过使用

SortedSet<T>

来实现，它允许使用

GetViewBetween

访问子集，它返回具有

SortedSet<T>

和

Min

属性的

Max

形状的视图：

public static T? CeilingEntry<T>(this SortedSet<T> set, T value) where T : IMinMaxValue<T>
{
    return set.GetViewBetween(value, T.MaxValue).Min;
}

public static T? FloorEntry<T>(this SortedSet<T> set, T value) where T : IMinMaxValue<T>
{
    return set.GetViewBetween(T.MinValue, value).Max;
}

使用示例：

var set = new SortedSet<int> { 2, 4, 6, 8, 10 };

Console.WriteLine($"Floor entry for 5: {set.FloorEntry(5)}"); // 4
Console.WriteLine($"Floor entry for 6: {set.FloorEntry(6)}"); // 6
Console.WriteLine($"Floor entry for 7: {set.FloorEntry(7)}"); // 6

Console.WriteLine($"Ceiling entry for 5: {set.CeilingEntry(5)}"); // 6
Console.WriteLine($"Ceiling entry for 6: {set.CeilingEntry(6)}"); // 6
Console.WriteLine($"Ceiling entry for 7: {set.CeilingEntry(7)}"); // 8

SortedSet<T>

性能特征没有记录，但由于实现是由红黑树支持的，因此插入和搜索（既是视图创建也是最小/最大访问）的操作复杂性是

O(log n)

。

如果想要类似字典的行为，可以通过存储单独的

Dictionary<TKey, TValue>

或使用键值结构来实现，其中只有键是比较的一部分，例如：

public readonly struct Entry<TKey, TValue> : IEquatable<Entry<TKey, TValue>>, IComparable<Entry<TKey, TValue>>
    where TKey : IMinMaxValue<TKey>, IEquatable<TKey>, IComparable<TKey>
{
    public TKey Key { get; }
    public TValue Value { get; }

    public Entry(TKey key, TValue value) => (Key, Value) = (key, value);

    // Only reflect Key in comparisons
    public bool Equals(Entry<TKey, TValue> other) => Key.Equals(other.Key);
    public int CompareTo(Entry<TKey, TValue> other) => Key.CompareTo(other.Key);

    public override string ToString() => $$"""{ Key = {{Key}}, Value = {{Value}} }""";
}

public static Entry<TKey, TValue>? CeilingEntry<TKey, TValue>(this SortedSet<Entry<TKey, TValue>> set, TKey key)
    where TKey : IMinMaxValue<TKey>, IEquatable<TKey>, IComparable<TKey>
{
    return set.GetViewBetween(new(key, default!), new(TKey.MaxValue, default!)).Min;
}

public static Entry<TKey, TValue>? FloorEntry<TKey, TValue>(this SortedSet<Entry<TKey, TValue>> set, TKey key)
    where TKey : IMinMaxValue<TKey>, IEquatable<TKey>, IComparable<TKey>
{
    return set.GetViewBetween(new(TKey.MinValue, default!), new(key, default!)).Max;
}

请注意，有大量的泛型。如果您将密钥限制为例如

int

，代码会简单一点。

用途：

var complexSet = new SortedSet<Entry<int, string>> { new(2, "two"), new(4, "four"), new(6, "six"), new(8, "eight"), new(10, "ten") };

Console.WriteLine($"Floor entry for 5: {complexSet.FloorEntry(5)}"); // { Key = 4, Value = four }
Console.WriteLine($"Floor entry for 6: {complexSet.FloorEntry(6)}"); // { Key = 6, Value = six }
Console.WriteLine($"Floor entry for 7: {complexSet.FloorEntry(7)}"); // { Key = 6, Value = six }

Console.WriteLine($"Ceiling entry for 5: {complexSet.CeilingEntry(5)}"); // { Key = 6, Value = six }
Console.WriteLine($"Ceiling entry for 6: {complexSet.CeilingEntry(6)}"); // { Key = 6, Value = six }
Console.WriteLine($"Ceiling entry for 7: {complexSet.CeilingEntry(7)}"); // { Key = 8, Value = eight }

我并不完全确定它的性能（如果它最终没有太多的泛型、堆栈数据的复制等，那么什么会被 JIT 虚拟化）。我将其包装成一个单独的类型，以避免暴露

default!

的丑陋，并拥有一个可以像

Dictionary<TKey, TValue>

一样处理键和值的 API。

如果需要搜索精确值，则

SortedSet<T>

具有

TryGetValue

应该可以解决问题，因为

Contains

在这种情况下不会很有用。