Binary tuple search list for closest value> =

Question

Given a:

List<Tuple<DateTime, int>>

If the list is listed sorted by value DateTime descending.

How can I use the method .BinarySearch()to find the smallest index value, where DateTime- >=than the specified value?

EG, with values:

[0] = 29th Jan
[1] = 25th Jan
[2] = 20th Jan
[3] = 10th Jan
[4] = 3rd Jan

Searching results:

1st Jan = return 4
5th Jan = return 3
28th Jan = return 0
1st Feb = return something else indicating nothing found (eg -1 or null)

Answer 1

Since your list is sorted in the reverse order that it expects BinarySearch, your comparison method needs to return the result of the date comparison:

class TupleCompare : IComparer<Tuple<DateTime,int>> {
    public static readonly TupleCompare Instance = new TupleCompare();
    public int Compare(Tuple<DateTime,int> x, Tuple<DateTime,int> y) {
        return -x.Item1.CompareTo(y.Item1); // Note the negative here
    }
}

Using this comparator, call BinarySearch, make sure its value is negative, invert its bits and subtract 1:

DateTime myDate = ... // desired date
int index = list.BinarySearch(Tuple.Create(myDate, 0), TupleCompare.Instance);
if (index < 0) {
    var res = ~index-1;
} else {
    Console.WriteLine("Exact match at index {0}", index);
}

Demo version

Answer 2

. .

List<DateTime> list = new List<DateTime>();

list.Add(Convert.ToDateTime("29 Jan"));
list.Add(Convert.ToDateTime("25 Jan"));
list.Add(Convert.ToDateTime("20 Jan"));
list.Add(Convert.ToDateTime("10 Jan"));
list.Add(Convert.ToDateTime("3 Jan"));

var comparer = Comparer<DateTime>.Create((x, y) => -x.CompareTo(y)); // notice negative
var search = Convert.ToDateTime("2 Jan");

var find = list.BinarySearch(search, comparer);
if (find < 0) find = ~find - 1; // minus 1 because ordered by descending

Console.WriteLine(find);

Answer 3

:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.IO.Ports;
using System.Data;

using System.Xml.Serialization;



namespace ConsoleApplication20
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Tuple<DateTime, int>> list = new List<Tuple<DateTime,int>>() {
                new Tuple<DateTime,int>(new DateTime(2018, 1,29),0),
                new Tuple<DateTime,int>(new DateTime(2018, 1,25),1),
                new Tuple<DateTime,int>(new DateTime(2018, 1,20),2),
                new Tuple<DateTime,int>(new DateTime(2018, 1,10),3),
                new Tuple<DateTime,int>(new DateTime(2018, 1,3),4)
            };


            List<DateTime> searchDates = new List<DateTime>() { new DateTime(2018, 1, 1), new DateTime(2018, 1, 5), new DateTime(2018, 1, 28), new DateTime(2018, 2, 1) };

            foreach(DateTime date in searchDates)
            {
                int results = BinarySearch(list, date);
                Console.WriteLine("Input Date : '{0}', index : '{1}'", date.ToShortDateString(), results);
            }
            Console.ReadLine();

        }
        static int BinarySearch(List<Tuple<DateTime, int>> list, DateTime date)
        {
            var results = list.Select(x => new { diff = (x.Item1 - date).Days, index = x.Item2 }).Where(x => x.diff >= 0).OrderBy(x => x.diff).FirstOrDefault();
            return results == null ? -1 : results.index;
        }




    }


}