如何用BinarySearch查找降序Tuple列表中>=指定DateTime的最小索引

首先，你的列表是按DateTime降序排列的，但List.BinarySearch()默认用的是升序比较逻辑，所以得自定义一个适配降序的比较器，再根据返回值规则推导目标索引。

核心思路 #

1. 自定义降序比较器：让BinarySearch()按照Tuple.Item1（DateTime）的降序来对比元素。
2. 处理BinarySearch()的返回值：
   • 如果找到匹配元素，要确认最后一个符合DateTime≥目标值的元素索引（避免多个相同DateTime的情况）。
   • 如果没找到匹配元素，通过返回的负值计算插入点，插入点的前一个位置就是最后一个DateTime≥目标值的元素索引；要是插入点为0，说明所有元素都小于目标值，返回未找到标识（比如-1）。

代码实现 #

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // 示例列表：按DateTime降序排列
        var dateList = new List<Tuple<DateTime, int>>
        {
            Tuple.Create(new DateTime(2024, 1, 29), 1),
            Tuple.Create(new DateTime(2024, 1, 25), 2),
            Tuple.Create(new DateTime(2024, 1, 20), 3),
            Tuple.Create(new DateTime(2024, 1, 10), 4),
            Tuple.Create(new DateTime(2024, 1, 3), 5)
        };

        // 测试示例场景
        Console.WriteLine(GetTargetIndex(dateList, new DateTime(2024, 1, 1))); // 输出4
        Console.WriteLine(GetTargetIndex(dateList, new DateTime(2024, 1, 5))); // 输出3
        Console.WriteLine(GetTargetIndex(dateList, new DateTime(2024, 1, 28))); // 输出0
        Console.WriteLine(GetTargetIndex(dateList, new DateTime(2024, 2, 1))); // 输出-1
    }

    static int GetTargetIndex(List<Tuple<DateTime, int>> sortedList, DateTime targetDate)
    {
        // 自定义降序比较器：仅对比Tuple的DateTime部分
        var descComparer = Comparer<Tuple<DateTime, int>>.Create((a, b) => 
            b.Item1.CompareTo(a.Item1)
        );

        // 构造临时搜索用的Tuple（Item2不影响比较结果）
        var searchItem = Tuple.Create(targetDate, 0);
        int searchResult = sortedList.BinarySearch(searchItem, descComparer);

        if (searchResult >= 0)
        {
            // 找到匹配元素，遍历找到最后一个相同DateTime的元素索引
            int lastMatchIndex = searchResult;
            while (lastMatchIndex + 1 < sortedList.Count && 
                   sortedList[lastMatchIndex + 1].Item1 == targetDate)
            {
                lastMatchIndex++;
            }
            return lastMatchIndex;
        }
        else
        {
            // 计算插入点：searchResult = -(插入点) -1 → 插入点 = -searchResult -1
            int insertionPoint = -searchResult - 1;
            // 插入点的前一位就是最后一个≥目标值的元素索引
            int targetIndex = insertionPoint - 1;
            
            // 若targetIndex小于0，说明没有元素符合条件
            return targetIndex >= 0 ? targetIndex : -1;
        }
    }
}

结果验证 #

完全匹配你给出的示例场景：

• 搜索1月1日：插入点是5（所有元素都≥1，插入到列表末尾），targetIndex=5-1=4，返回4。
• 搜索1月5日：插入点是4（5应插入到10和3之间），targetIndex=4-1=3，返回3。
• 搜索1月28日：插入点是1（28应插入到29和25之间），targetIndex=1-1=0，返回0。
• 搜索2月1日：插入点是0（所有元素都小于2月1日，插入到列表开头），targetIndex=0-1=-1，返回-1（未找到）。

注意事项 #

• 必须确保输入列表已经严格按照DateTime降序排列，否则BinarySearch会失效。
• 如果列表中有多个相同DateTime的元素，代码会返回最后一个（索引最大）的那个，正好对应“≥目标值的元素中DateTime最小的那个”的需求。

内容的提问来源于stack exchange，提问作者Tom Gullen