如何在List<T>.BinarySearch中有效地复制ArrayList.BinarySearch？

Question

我正在尝试将一个旧项目从使用ArrayList集合升级到使用List集合。除了将ArrayList.BinarySearch转换为List之外，一切都很顺利。虽然List有一个相应的方法，但是ArrayList.BinarySearch有一个重载，它接受一个任意对象，而List.BinarySearch则要求T类型的对象。以下是示例。

我如何有效地用List替换这个ArrayList功能？或者我必须自己写一个新函数吗？

class Pod {
   public DateTime Start { get; set; }
}

class TimeRange: IComparer {
    TimeSpan StartsAt { get; set; }
    ITimeRangeComparer TimeComparer { get; set; }
    public int Compare(object x, object y) {
       // there is more to it, but basically compares time ranges
       return comparer.Compare((TimeRange) x, (TimeRange) y);
    }        
}

class Manager {
   void DoStuff() {
        ArrayList alPods = GetPodsAL();
        List<Pod> lstPods = GetPodsLST();
        int stopIndex;

        TimeRange startPoint = GetStartPoint();
        TimeRange stopPoint = GetStopPoint();

        // ArrayList works fine
        stopIndex = alPods.BinarySearch(stopPoint, startPoint.TimeComparer);

        // Fails because the method demands that `stopPoint` be of type Pod
        stopIndex = lstPods.BinarySearch(stopPoint, startPoint.TimeComparer);
   }
}

- AngryHacker

---

如果你有一个 List<T>，为什么要传入一个不是类型 T 的对象呢？这样的对象可能不在列表中。 - Adam Robinson

只需为List<T>编写自己的BinarySearch扩展方法，该方法将接受任意对象，这应该很容易。 - Dmitry Osinovskiy

@Dmitry Osinovskiy提出了一个不错的想法（创建扩展）。个人而言，我尽量避免使用扩展方法。我认为你应该投入更多时间来重构你的代码，并使用通用比较器的BinarySearch。 - Jean-Philippe Leclerc

@AngryHacker，只需从http://en.wikibooks.org/wiki/Algorithm_Implementation/Search/Binary_search#C.23_.28common_Algorithm.29获取代码，并将int[]更改为List<T>，int更改为object，添加IComparer作为单独的参数，将==和<更改为调用比较器。或者使用dotPeek / ReSharper并反汇编ArrayList.BinarySearch。 - Dmitry Osinovskiy

我认为你想要的是一个接受 Func<T, int> 的 BinarySearch 版本。这是最通用的二分查找版本，但框架不提供它 :( - usr

Answer 1

为了使用与 ArrayList.BinarySearch 相同的方法，将您的 List<T> 转换为数组，并调用 Array.BinarySearch(Array, object)。不幸的是，您需要将其转换/复制到一个新数组中。

List<SomeType> list;
SomeType value;
// ...
Array.BinarySearch(list.ToArray(), value)

我确实质疑你的方法，因为 List<T> 是强类型的，它只能包含类型 T。如果你不确定列表中的类型是否是这个类型，那么事先检查或编写扩展方法来执行此操作。

public static class ListExtensionMethods
{
    public static int BinarySearch<T>(this List<T> list, object value)
    {
        if (value is T)
            return list.BinarySearch((T)value);
        return -1;
    }
}

- Daniel Imms