最接近值的元组的二进制搜索列表 >=

Question

给定一个：

List<Tuple<DateTime, int>>

提供的列表按 DateTime 值 descending 排序。

如何使用 .BinarySearch() 方法找到 DateTime 比指定值 >= 的值的最小索引？

EG，值：

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

搜索结果为：

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

由于您的列表顺序与 BinarySearch 预期相反，因此您的比较方法需要 return 日期比较结果的倒数：

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

有了这个比较器，调用 BinarySearch，检查它的值是否为负，反转它的位，然后减去 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.

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




    }


}

最接近值的元组的二进制搜索列表 >=

Binary search list of Tuples for nearest value >=

c#

datetime

binary-search