如何二进制搜索面板列表

Question

我有一个面板列表，按它们的 y 值排序。您可以查看以了解为何以这种方式构建的具体细节。长话短说，这个列表在位置 0 有最高的面板，在它下面的位置 1，等等，直到最后一个位置的最后一个。我正在使用根据我的链接问题改编的这行代码访问每个面板的 y 坐标：

Panel p = panelList[someIndex];
int panelHeight = p.Top + p.Parent.Top - p.Parent.Margin.Top;
//The above line guarantees that the first panel (index 0) has y-coordinate 0 when scrolled all the way up,
//and becomes negative as the user scrolls down.
//the second panel starts with a positive y-coordinate, but grows negative after the user scrolls past the top of that page
//and so on...

我需要找到面板的索引最接近 高度 0，这样我就知道哪些面板当前在页面上，或者非常接近页面。因此，我正在尝试使用 List.BinarySearch() 方法，这是我被困的地方。我希望利用 BinarySearch 的属性返回值在列表中存在时所处的索引。这样我就可以搜索高度为 0 的面板（我不希望找到），但找到离它最近的元素（比如在 y=24 或 y=-5 处），并且知道那是面板正在渲染中。

Binary Search 允许您指定一个 IComparer 来定义 < 和 > 操作，所以我写了这个 class:

class PanelLocationComparer : IComparer<Panel>
{
    public int Compare(Panel x, Panel y)
    {
        //start by checking all the cases for invalid input
        if      (x == null && y == null) { return  0; }
        else if (x == null && y != null) { return -1; }
        else if (x != null && y == null) { return  1; }
        else//both values are defined, compare their y values
        {
            int xHeight = x.Top + x.Parent.Top - x.Parent.Margin.Top;
            int yHeight = y.Top + y.Parent.Top - y.Parent.Margin.Top;
            if (xHeight > yHeight)
            {
                return 1;
            }
            else if (xHeight < yHeight)
            {
                return -1;
            }
            else
            {
                return 0;
            }
        }
    }
}

那行不通，我现在意识到这是因为比较两个面板的大于或小于实际上并不关心我正在搜索的值，在这种情况下 y 值 = 0. 有没有办法在 IComparer 中实现它，或者有没有办法使用内置的 BinarySearch 进行这种类型的搜索？

我考虑过每次都制作一个与我的面板列表长度相同的新列表，将 y 值复制到其中，然后在这个整数列表中搜索 0，但是创建、搜索和销毁它list 每次滚动都会严重影响性能，以至于破坏了二进制搜索的意义。

我的问题是 also related to this one，但我不知道如何调整它，因为他们最终使用了一种内置的比较方法，在这种情况下我无法访问它。

Answer 1

不幸的是，内置的 BinarySearch 方法无法处理这种情况。他们所能做的就是搜索列表 item 或可以从列表 item 中提取的内容。有时它们可以与假货和适当的比较器一起使用，但这在这里不适用。

从另一方面来说，二分搜索是一种非常简单的算法，因此您可以轻松地为您的特定情况创建一个，或者更好的是，创建一个自定义扩展方法，以免下次您需要类似的东西时重复自己:

public static class Algorithms
{
    public static int BinarySearch<TSource, TValue>(this IReadOnlyList<TSource> source, TValue value, Func<TSource, TValue> valueSelector, IComparer<TValue> valueComparer = null)
    {
        return source.BinarySearch(0, source.Count, value, valueSelector, valueComparer);
    }
    public static int BinarySearch<TSource, TValue>(this IReadOnlyList<TSource> source, int start, int count, TValue value, Func<TSource, TValue> valueSelector, IComparer<TValue> valueComparer = null)
    {
        if (valueComparer == null) valueComparer = Comparer<TValue>.Default;
        int lo = start, hi = lo + count - 1;
        while (lo <= hi)
        {
            int mid = lo + (hi - lo) / 2;
            int compare = valueComparer.Compare(value, valueSelector(source[mid]));
            if (compare < 0) hi = mid - 1;
            else if (compare > 0) lo = mid + 1;
            else return mid;
        }
        return ~lo; // Same behavior as the built-in methods
    }
}

然后简单地使用：

int index = panelList.BinarySearch(0,  p => p.Top + p.Parent.Top - p.Parent.Margin.Top);

如何二进制搜索面板列表

How to binary search a list of Panels

c#

arraylist

binary-search

winforms