.NET是否有现成的二分查找类适用于KeyValuePair<K,V>？

Question

在我的Unity3d应用程序中，我需要检测用户选择的折线。确定方法是为每个GameObject(折线)添加一个碰撞器组件，这样我就知道每当用户点击一条折线时。但是，这样做效率非常低，因为我将有数千条折线。

因此，我更有效的方法是将每条折线从点(0,0,0)的距离存储在一个List <KeyValuePair<double,GameObject>>中。这个列表将按最低到最高的距离排序。当用户在游戏中选择一个点时，我将确定这个点距离(0,0,0)的距离(D)，然后使用“上界”二分查找来找到最接近该点的折线(即与(0,0,0)的距离类似的折线)。

我的问题是：在我重新发明轮子之前，是否有一个C#.NET类来执行“上界”二分查找算法、元素排序等？我知道有一个List(T).BinarySearch()方法，但是我需要确保List被正确地排序吗？如果我的列表没有排序，而该方法需要对列表进行排序，则可能效率很低。

- Mack

---

只是为了确认您最后一段话，来自 MSDN 的说明：“List<T> 必须根据比较器实现进行排序；否则，结果将不正确。” - Steven Liekens

你尝试过使用 SortedList<TKey, TValue>/SortedDictionary<TKey, TValue> 吗？来自 MSDN 的描述：'SortedList<TKey, TValue> 泛型类是一个具有 O(log n) 检索的键值对数组。' 不过请注意，只能插入唯一的键。 - Caramiriel

Answer 1

您可以使用SortedList<double, GameObject>来存储已排序的多边形，而不是使用List <KeyValuePair<double,GameObject>>。或者在所有多边形添加后对List<>进行一次排序（如果您显然不打算添加其他多边形，则第二个选项是最佳选择）。

@LeakyCode 提供了一个实现IList的下限，这将为您提供最接近GameObject的索引（在列表中）。

private static int BinarySearch<T>(IList<T> list, T value)
{
    if (list == null)
        throw new ArgumentNullException("list");
    var comp = Comparer<T>.Default;
    int lo = 0, hi = list.Length - 1;
    while (lo < hi) {
            int m = (hi + lo) / 2;  // this might overflow; be careful.
            if (comp(list[m], value) < 0) lo = m + 1;
            else hi = m - 1;
    }
    if (comp(list[lo], value) < 0) lo++;
    return lo;
}

public static int FindFirstIndexGreaterThanOrEqualTo<T,U>
                          (this SortedList<T,U> sortedList, T key)
{
    return BinarySearch(sortedList.Keys, key);
}

- quantdev

Answer 2

你应该先使用 List<T>.Sort 方法对列表进行排序，并在一个类中实现自己的 IComparer<T>。我认为这是最好的方法。

IComparer 参考 ISort 参考

- ZeroWorks