列表&lt；T&gt；二进制搜索返回错误的值 [英] List<T> Binary search returns wrong value

问题描述

即使列表已排序，对分搜索也会返回错误的值。列表如下：

1707 ABCD
1707 XXXX
1725 DEFG
1725 HIJK
1725 LMNOP

我是从按照时间(第一列)预先排序的文件中获得这个列表的，所以我不会在代码中对它进行排序。当我对1725 DEFG执行二进制搜索时，它在逐位补码之前返回1725 LMNOP。如果我按位求补，结果将是1725 HIJK。

为什么？

实现如下：

 public class RecComparer: IComparer<MyData>
{
 public  int Compare(MyData x, MyData y)
{
    if (x.DateDetails == null)
    {
        if (y.DateDetails == null)
        {
                           return 0;
        }
        else
        {

            return -1;
        }
    }
    else
    {

        if (y.DateDetails == null)
                      {
            return 1;
        }
        else
        {
            int retval = x.DateDetails.Length.CompareTo(y.DateDetails.Length);

            if (retval != 0)
            {

                return retval;
            }
            else
            {

                return x.DateDetails.CompareTo(y.DateDetails);
            }
        }
    }
}
}

下面是对BinarySearch的调用：

lookAhead = recordList.BinarySearch(lookAheadtime, (IComparer<MyData>)rc);

任何原因都是它会这样做的原因。

编辑：

public class MyData
{
    public string DateDetails { get; set; }
    public string TrackDetails { get; set; }
}

推荐答案

更新2：在具有重复项的列表中使用自定义比较器进行二进制搜索。

假设在"1707 ABCD"中，"1707"是DateDetails，"ABCD"是TrackDetails，您有一个数据数组，其中两个字段已经按其中一个的顺序排序，即DateDetails。因此，可能有多个条目具有相同的DateDetails。

如果执行BinarySearch，它将返回具有指定DateDetails、的条目之一，而不一定是第一个。然后您必须向后扫描才能找到第一个。

public static class ListHelper
{
    /// <summary>
    /// Return the zero-based index of the first matching item in the sorted List, 
    /// if a match for item is found; otherwise, a negative number that is the bitwise 
    /// complement of the index of the next element that is larger than item or, if there is
    /// no larger element, the bitwise complement of Count.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="list"></param>
    /// <param name="item"></param>
    /// <param name="comparer"></param>
    /// <returns>The zero-based index of the first matching item in the sorted List, 
    /// if item is found; otherwise, a negative number that is the bitwise complement 
    /// of the index of the next element that is larger than item or, if there is
    /// no larger element, the bitwise complement of Count.</returns>
    public static int BinarySearchFirst<T>(this List<T> list, T item, IComparer<T> comparer)
    {
        int start = list.BinarySearch(item, comparer);
        for (; start > 0 && comparer.Compare(list[start], list[start - 1]) == 0; start--)
            ;
        return start;
    }
    /// <summary>
    /// Find the zero-based indices of the first and last matching items in the sorted List, 
    /// if a match for item is found; otherwise, a negative number for both that is the bitwise 
    /// complement of the index of the next element that is larger than item or, if there is
    /// no larger element, the bitwise complement of Count.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="list"></param>
    /// <param name="item"></param>
    /// <param name="comparer"></param>
    /// <param name="start">The zero-based index of the first matching item in the List, 
    /// if item is found; otherwise, a negative number that is the bitwise complement 
    /// of the index of the next element that is larger than item or, if there is
    /// no larger element, the bitwise complement of Count.</param>
    /// <param name="end">The zero-based index of the first matching item in the sorted List, 
    /// if item is found; otherwise, a negative number that is the bitwise complement 
    /// of the index of the next element that is larger than item or, if there is
    /// no larger element, the bitwise complement of Count.</param>
    /// <returns>true if found, else false</returns>
    public static bool BinarySearchRange<T>(this List<T> list, T item, IComparer<T> comparer, out int start, out int end)
    {
        start = end = list.BinarySearch(item, comparer);
        if (start < 0)
            return false;
        for (; start > 0 && comparer.Compare(list[start], list[start - 1]) == 0; start--)
            ;
        for (int last = list.Count - 1; end < last && comparer.Compare(list[end], list[end + 1]) == 0; end++)
            ;
        return true;
    }
}

这篇关于列表&lt；T&gt；二进制搜索返回错误的值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！