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

Question

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

List<CurrencyHistoricExchangeRate> history = GetOrderedHistory();

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

How would I write a binary search function to replace this method? I'm struggling to implement it for an inexact comparison like this.

This method is called frequently, and can contain several thousand records which is why I wish to replace it with a binary search.

Answer 1

Given a sorted list, List<T>.BinarySearch actually helps you find the index of item which is "equal", or "larger than" your item (presuming an ascending list and a default comparer).

This method returns:

• The zero-based index of item in the sorted List, if item is found;
• or, a negative number that is the bitwise complement of the index of the next element that is larger than item
• or, if there is no larger element, the bitwise complement of Count.

So, first you need an inverted comparer, because your items are sorted in reverse:

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);
    }
}

Then, you need to check if the item was actually found or not, and complement the result:

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

Interpreting these results should then be something like:

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

After playing round with it 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];