C#：获取降序列表插入元素的索引，求更优实现方案

你的现有代码采用线性遍历查找插入位置，时间复杂度为O(n)，当列表元素较多时效率偏低。可以利用二分查找（时间复杂度O(logn)）来简化代码并提升执行效率，同时修正原代码中可能破坏降序排列的逻辑问题。

核心思路 #

.NET的List<T>内置了BinarySearch方法，但默认适配升序列表。我们可以通过自定义比较器让它支持降序场景，再根据方法返回值计算正确的插入索引。

BinarySearch的返回规则：

• 找到匹配元素时，返回该元素的索引；
• 未找到匹配元素时，返回-(插入点) - 1，其中插入点是列表中第一个小于目标元素的位置（降序场景下）。

实现代码 #

方法1：自定义比较器（适用于需要复用的场景）

// 针对int类型的降序比较器，可替换为你的元素类型
public class DescendingIntComparer : IComparer<int>
{
    public int Compare(int x, int y)
    {
        // 反转默认的升序逻辑，实现降序比较
        return y.CompareTo(x);
    }
}

// 插入逻辑方法
int InsertIntoDescendingList(List<int> mylist, int item)
{
    int index = mylist.BinarySearch(item, new DescendingIntComparer());
    // 处理未找到匹配元素的情况，计算插入点
    if (index < 0)
    {
        index = ~index;
    }
    mylist.Insert(index, item);
    return index;
}

方法2：匿名比较器（代码更紧凑，C# 4.0+支持）

如果无需复用比较器，可直接创建匿名比较器，省去单独定义类的步骤：

int InsertIntoDescendingList(List<int> mylist, int item)
{
    var descendingComparer = Comparer<int>.Create((x, y) => y.CompareTo(x));
    int index = mylist.BinarySearch(item, descendingComparer);
    // 统一处理找到/未找到的情况
    index = index >= 0 ? index : ~index;
    mylist.Insert(index, item);
    return index;
}

关键说明 #

1. 自定义比较器通过y.CompareTo(x)反转默认的升序逻辑，让BinarySearch按照降序规则执行查找；
2. 当BinarySearch返回负数时，~index是-(index + 1)的简化写法，可直接得到正确的插入位置；
3. 代码无需额外判断列表是否为空——空列表时BinarySearch返回-1，~-1=0，会自动插入到索引0的位置。

修复原代码的逻辑问题 #

原代码的判断条件item < mylist[i]会破坏降序排列（比如向[5,3,2]插入4时，会错误地插入到索引0，得到[4,5,3,2]）。上述二分查找方案会自动定位到正确位置，插入后列表始终保持降序。

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