Date search binary list for highest date, where date <= n

Question

Given a list of dates in descending order, this code will find the largest date when the date is <= searchDate.

List<CurrencyHistoricExchangeRate> history = GetOrderedHistory();

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

How do I write a binary search function to replace this method? I am struggling to implement it for an inaccurate comparison like this.

This method is called frequently and may contain several thousand entries, so I want to replace it with a binary search.

Answer 1

After playing with him a bit, I came up with this working solution:

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];

Answer 2

, List<T>.BinarySearch , "", "" ( ).

:

• , ;
• , , ,
• , , 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}");