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

Question

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

List<CurrencyHistoricExchangeRate> history = GetOrderedHistory();

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

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

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

Answer 1

给定一个排序列表，List<T>.BinarySearch 实际上可以帮助您找到 "equal" 或 "larger than" 您的项目的索引（假定一个升序列表和一个默认比较器）。

这个方法returns:

排序列表中项目的从零开始的索引，如果找到项目；
或者，一个负数，它是 下一个大于 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];

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

Binary search list of dates for largest date where date <= n

c#

date

binary-search