Does .NET have an existing search binary class for KeyValuePair <K, V>

Question

In my Unity3d application, I need to define the polyline selected by the user. An easy way to determine this is to add a collider component to each GameObject (polyline), then I will know when the user clicks on the polyline. But this is incredibly inefficient because I will have thousands of polylines.

So my more efficient method is to keep every distance of the polylines from the point (0,0,0) in List <KeyValuePair<double,GameObject>>. This list will be ordered from the lowest distance to the highest. When the user selects a point in the game, I determine the distance (D) of these points from (0,0,0), then use the "Top Boundaries" Binary Searchto find the closest polyline to this point (i.e., C is the same distance to (0, 0,0)).

My question is: . Before I go over and reinvent the wheel and code my own binary “Top Boundary” search algorithm, sorting elements, etc., is there a C # .NET class for binary search Upper Bounds that will sort and search for me?

I know the method List(T).BinarySearch(), but does it depend on what Listis sorted correctly? If my list is not sorted, and the method should sort the list, each method call can be quite inefficient.

Answer 1

You can use SortedList<double, GameObject>to store sorted polygons instead List <KeyValuePair<double,GameObject>>. Or you Sort () yours List<>once after all the polygons have been added (the second option is better if you are not going to add other polygons last, obviously).

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

Answer 2

, List<T>.Sort IComparer<T> . , .

IComparer ISort