c# - 日期 <= n 的最大日期的二进制搜索日期列表

Question

给定一个按降序排列的日期列表，此代码将找到日期为 <= searchDate 的最大日期.

List<CurrencyHistoricExchangeRate> history = GetOrderedHistory();

foreach (var record in history)
{
    if (record.Date < searchDate)
    {
        return record ;
    }
}

我将如何编写二分查找函数来替换此方法？我正在努力实现这样一个不精确的比较。

这个方法被频繁调用，可以包含几千条记录，所以我想用二分查找来代替它。

Answer 1

给定一个排序列表，List<T>.BinarySearch实际上可以帮助您找到“等于”或“大于”您的项目的项目索引(假定升序列表和默认比较器)。

此方法返回:

• 如果找到项目，则排序列表中项目的从零开始的索引；
• 或者，一个负数，它是下一个大于 item 的元素的索引的按位补码
• 或者，如果没有更大的元素，Count 的按位补码。

所以，首先你需要一个倒排比较器，因为你的项目是倒序排列的:

class CurrencyHistoricExchangeRateComparer : IComparer<CurrencyHistoricExchangeRate>
{
    public int Compare(CurrencyHistoricExchangeRate x, CurrencyHistoricExchangeRate y)
    {
        // this is just the opposite of the default DateTime comparer
        return -x.Date.CompareTo(y.Date);
    }
}

然后，您需要检查是否确实找到了该项目，并对结果进行补充:

private static int FindIndex(List<CurrencyHistoricExchangeRate> list, DateTime dateTime)
{
    var comparer = new CurrencyHistoricExchangeRateComparer();
    var idx = list.BinarySearch(
        new CurrencyHistoricExchangeRate() { Date = dateTime }, comparer);

    // not found? then calculate the bitwise complement to 
    // get the index of the first larger element 
    // (this will evaluate to list.Count if there is no such element)
    return (idx < 0) ? ~idx : idx;
}

然后解释这些结果应该是这样的:

var idx = FindIndex(history, someDate);

CurrencyHistoricExchangeRate rate = null;
if (idx < history.Count)
    rate = history[idx];
else
    throw new InvalidOperationException($"there are no dates smaller than {someDate}");