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

Question

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

List<CurrencyHistoricExchangeRate> history = GetOrderedHistory();

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

如何编写二进制搜索函数来替换此方法？我正在努力实现它,因为这样的不精确比较.

这种方法经常被调用,并且可以包含几千条记录,这就是我希望用二进制搜索替换它的原因.

Answer 1

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

该方法返回：

• 如果找到 item，则排序列表中 item 的从零开始的索引；
• 或者，一个负数，它是大于 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}");

Answer 2

经过一番研究后，我想出了这个可行的解决方案：

if (history.First().Date <= date) return history.First();

var lowerIx = 0;
var upperIx = history.Count - 1;
while (true)
{
    var middleIndex = lowerIx + (upperIx - lowerIx) / 2;

    if (history[middleIndex].Date <= date)
    {
        upperIx = middleIndex;
    }
    else
    {
        lowerIx = middleIndex;
    }

    if (lowerIx + 1 == upperIx) break;
}
if(history[upperIx].Date > date) throw new Exception();
return history[upperIx];