如何获得二叉查找结果的第一个索引

本文关键字：第一个 索引 结果 查找 何获得 | 更新日期: 2023-09-27 18:15:50

我有一些问题。我有两个列表，如:

List<int> firstList = new List<int> { 1, 2, 2, 3, 5};
List<int> secondList = new List<int> { 2, 3, 1 };

⇒True result为:{1, 3, 0}

我想获得firstList中存在的secondList中的第一个数字索引。我使用list.BinarySearch()，但结果是{2, 3, 0}。

如何获得二叉查找结果的第一个索引

  List<int> firstList = new List<int> { 1, 2, 2, 3, 5};
  List<int> secondList = new List<int> { 2, 3, 1 };
  var output = secondList.Select(item => firstList.IndexOf(item)); // [1 , 3 , 0]

您可以用BinarySearch逻辑替换IndexOf，但是BinarySearch返回第一个匹配的元素索引，所以您不会得到最低的数字，IndexOf返回最低匹配的索引。

问题是，当列表包含重复的值时，如您的情况，BinarySearch方法将返回任何匹配值的索引(不确定)。

要获得想要的结果，您可以创建并使用一个自定义扩展方法，如下所示:

public static class ListExtensions
{
    public static int BinarySearchFirst<T>(this List<T> source, T item, IComparer<T> comparer = null)
    {
        if (comparer == null) comparer = Comparer<T>.Default;
        int index = source.BinarySearch(item, comparer);
        while (index > 0 && comparer.Compare(source[index], source[index - 1]) == 0)
            index--;
        return index;
    }
}
示例用法:

var result = secondList.Select(x => firstList.BinarySearchFirst(x)).ToList();
// { 1, 3, 0 }

c++有一个标准库函数，叫做lower_bound()。

这是一个c#实现。这在搜索大型集合时非常有用:

public static int LowerBound<T>(IList<T> values, T target, int first, int last) 
    where T : IComparable<T>
{
    int left = first;
    int right = last;
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        var middle = values[mid];
        if (middle.CompareTo(target) < 0)
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}

对于没有找到的元素不会返回-1，所以为了解决这个问题，我们可以像这样包装它:

public static int LowerBoundOrMinusOne<T>(IList<T> values, T target, int first, int last)
    where T : IComparable<T>
{
    int result = LowerBound(values, target, first, last);
    if (result >= last || result < first || values[result].CompareTo(target) != 0)
        return -1;
    return result;
}

用法如下:

List<int> firstList = new List<int> { 1, 2, 2, 3, 5 };
List<int> secondList = new List<int> { 2, 3, 1 };
List<int> result = secondList
    .Select(value => LowerBoundOrMinusOne(firstList, value, 0, firstList.Count))
    .ToList();
Console.WriteLine(string.Join(", ", result));

当然，这主要是对大列表的好处，因为它具有O(Log2(N))而不是O(N)的复杂度。

遍历第二个数组并获取第一个数组元素的索引:

foreach (int item in secondList)
{
    Console.WriteLine(firstList.IndexOf(item));
}

如果你有一个大的firstList，所以你必须使用BinarySearch尝试修改它:通过BinarySearch找出项目(这是不保证是最左边的一个)，然后移动到左边，同时读取相同的项目:

  List<int> firstList = new List<int> { 1, 2, 2, 3, 5 };
  List<int> secondList = new List<int> { 2, 3, 1, 123 };
  var result = secondList
    .Select(item => firstList.BinarySearch(item))
    .Select(index => index < 0 ? -1 : Enumerable
       .Range(0, index + 1)     // we have to scan [0..index] at the worst case
       .Select(i => index - i)  // scan in reverse
       .TakeWhile(i => firstList[index] == firstList[i]) // take while items are the same
       .Last()); // finally, we want the last item

测试
  // 1, 3, 0, -1
  Console.Write(String.Join(", ", result));
相关文章：