Does .NET have an existing binary search class for KeyValuePair

Question

In my Unity3d application, I need to detect a polyline that has been selected by a user. The easy way to determine this is to add a collider component to each GameObject (polyline) then I'll know whenever the user clicks a polyline. But this is incredibly inefficient because I will have thousands of polylines.

So my more efficient method is to store each polylines distance from the point (0,0,0) in a List <KeyValuePair<double,GameObject>>. This list will be ordered from lowest distance to highest. When the user selects a point in the game, I will determine this points' distance (D) from (0,0,0) then use a 'Upper Bounds' Binary Search to find the polyline closest to this point (ie, with a similar distance to (0,0,0)).

My Question: Before I go and reinvent the wheel and code my own 'Upper Bounds' Binary Search algorithm, element sorting and etc, is there a C# .NET class for Upper Bounds Binary Search that will sort and search for me?

I am aware of the method List(T).BinarySearch() but is it up to me to ensure that the List is sorted correctly? If my list isn't sorted, and the method needs to sort the list each method call then that could be rather inefficient.

Just to confirm your last paragraph, from MSDN: "The List must already be sorted according to the comparer implementation; otherwise, the result is incorrect." — Steven Liekens, Jun 05 '14 at 06:21
Have you tried using `SortedList`/`SortedDictionary`? From MSDN: 'The SortedList generic class is an array of key/value pairs with O(log n) retrieval'. Though note that only unique keys can be inserted. — Caramiriel, Jun 05 '14 at 06:22

score 1 · Answer 1 · edited May 23 '17 at 10:26

You could use a SortedList<double, GameObject> to store your polygons sorted instead of List <KeyValuePair<double,GameObject>> . Or you Sort() your List<> once after all polygons have been added (the second option is the best if you are not going to add other polygons latter, obviously).

@LeakyCode provided an implementation of lower bound for an IList, which would give you the index (in your list) of the closest 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);
}

score 0 · Answer 2 · answered Jun 05 '14 at 06:20

0

Should you sort your list first using List<T>.Sort Method and implement our own IComparer<T> in a class. I think it's the best approach.

References to IComparer Reference to ISort

answered Jun 05 '14 at 06:20

ZeroWorks

1,618
1
18
22

Does .NET have an existing binary search class for KeyValuePair

2 Answers2