c# - C#-自定义类字符串列表的二进制搜索算法

基本上，我需要帮助调整我的二进制搜索算法来处理我的字符串列表，如下所示。注意，我必须使用一个书面的二进制搜索算法，不使用内置的c#函数，如.Binary Search。
现在我将向您展示列表的格式和列表本身：

// This class formats the list, might be useful to know

public class Demo
{
    public string Col;
    public string S1;
    public string S2;
    public string S3;

    public override string ToString()
    {
        return string.Format("Col: {0}, S1: {1}, S2: {2}, S3: {3}", Col, S1, S2, S3);
    }
}

// The list itself

var list = new List<Demo>
        {
            new Demo {Col = "Blue", S1 ="88", S2 ="Yes"},
            new Demo {Col = "Green", S1 ="43", S2 ="Yes"},
            new Demo {Col = "Red", S1 ="216", S2 ="No"},
            new Demo {Col = "Yellow", S1 ="100", S2 ="No"}
        };

列表已经按“Col”字符串值的字母顺序排序，因此为什么蓝色是第一个，黄色是最后一个“col”是列表中需要搜索的部分。下面我插入了当前的二进制搜索，它可以搜索int数组。

public static int BinarySearch_R(int key, int[] array, int low, int high)
    {
        if (low > high) return -1;
        int mid = (low + high) / 2;
        if (key == array[mid])
        {

            return mid;
        }
        if (key < array[mid]) {
            return BinarySearch_R(key, array, low, mid - 1);
        } else {
            return BinarySearch_R(key, array, mid + 1, high);
        }
    }

我需要帮助调整我的BinarySearch算法以适应上面的列表。如果你们有任何问题，或者需要看更多我的代码，只要问。

最佳答案

具体的回答是：根据具体情况调整你的方法是很容易的。
首先更新现有的方法，使用更一般的方法（AA>比较，而不是IComparable<T>.CompareTo操作符：

public static int BinarySearch_R(int key, int[] array, int low, int high)
{
    if (low > high) return -1;
    int mid = (low + high) / 2;
    int compare = key.CompareTo(array[mid]);
    if (compare == 0)
    {
        return mid;
    }
    if (compare < 0)
    {
        return BinarySearch_R(key, array, low, mid - 1);
    }
    else {
        return BinarySearch_R(key, array, mid + 1, high);
    }
}

然后，您只需复制/粘贴上述方法，将int替换为int key，string key替换为int[] array，List<Demo> array替换为array[mid]，array[mid].Col替换为int[]：

public static int BinarySearch_R(string key, List<Demo> array, int low, int high)
{
    if (low > high) return -1;
    int mid = (low + high) / 2;
    int compare = key.CompareTo(array[mid].Col);
    if (compare == 0)
    {
        return mid;
    }
    if (compare < 0)
    {
        return BinarySearch_R(key, array, low, mid - 1);
    }
    else {
        return BinarySearch_R(key, array, mid + 1, high);
    }
}

扩展回答：虽然您可以执行上述操作，但它将要求您对任何其他需要此类功能的属性/类执行相同的操作。
更好的方法是泛化代码例如，可以将List<Demo>和IReadOnlyList<T>概括为int/string key，TKey key概括为Demo.Col，Func<T, TKey>概括为CompareTo，IComparer<TKey>.Compare概括为List<Demo>，因此最终的通用方法可以如下：

public static class MyAlgorithms
{
    public static int BinarySearch<T, TKey>(this IReadOnlyList<T> source, Func<T, TKey> keySelector, TKey key, IComparer<TKey> keyComparer = null)
    {
        return source.BinarySearch(0, source.Count, keySelector, key, keyComparer);
    }

    public static int BinarySearch<T, TKey>(this IReadOnlyList<T> source, int start, int count, Func<T, TKey> keySelector, TKey key, IComparer<TKey> keyComparer = null)
    {
        // Argument validations skipped
        if (keyComparer == null) keyComparer = Comparer<TKey>.Default;
        int lo = start, hi = start + count - 1;
        while (lo <= hi)
        {
            int mid = lo + (hi - lo) / 2;
            int compare = keyComparer.Compare(key, keySelector(source[mid]));
            if (compare < 0)
                hi = mid - 1;
            else if (compare > 0)
                lo = mid + 1;
            else
                return mid;
        }
        return -1;
    }
}

现在，您可以对任何数据结构使用该方法。例如，按Col搜索您的将如下所示：

int index = list.BinarySearch(e => e.Col, "Red");

关于c# - C#-自定义类字符串列表的二进制搜索算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36663681/