在C#中进行范围查找-如何实现

本文关键字：何实现 实现 查找 范围 | 更新日期: 2023-09-27 18:21:00

我正在努力了解如何实现Jon Skeet在线程中发现的代码：在C#中查找范围？

有人能用这样的东西提供一个设置示例吗：1-10000、10001-40000、40000+

第一组返回的值分别为1、2、3，在哪里？

我不太清楚这段代码是如何做到的。tx.

public interface IRangeComparer<TRange, TValue>
{
    /// <summary>
    /// Returns 0 if value is in the specified range;
    /// less than 0 if value is above the range;
    /// greater than 0 if value is below the range.
    /// </summary>
    int Compare(TRange range, TValue value);
}

/// <summary>
/// See contract for Array.BinarySearch
/// </summary>
public static int BinarySearch<TRange, TValue>(IList<TRange> ranges,
                                               TValue value,
                                               IRangeComparer<TRange, TValue> comparer)
{
    int min = 0;
    int max = ranges.Count-1;
    while (min <= max)
    {
        int mid = (min + max) / 2;
        int comparison = comparer.Compare(ranges[mid], value);
        if (comparison == 0)
        {
            return mid;
        }
        if (comparison < 0)
        {
            min = mid+1;
        }
        else if (comparison > 0)
        {
            max = mid-1;
        }
    }
    return ~min;
}

在C#中进行范围查找-如何实现

您需要很好地掌握泛型才能理解此代码。这里有一个功能实现：

public class Range<TValue> 
    where TValue : IComparable<TValue>
{
    public TValue Min { get; set; }
    public TValue Max { get; set; }
    public Range(TValue min, TValue max)
    {
        this.Min = min;
        this.Max = max;
    }
}
public class RangeComparer<TValue> : IRangeComparer<Range<TValue>, TValue> 
    where TValue : IComparable<TValue>
{
    /// <summary>
    /// Returns 0 if value is in the specified range;
    /// less than 0 if value is above the range;
    /// greater than 0 if value is below the range.
    /// </summary>
    public int Compare(Range<TValue> range, TValue value)
    {
        // Check if value is below range (less than min).
        if (range.Min.CompareTo(value) > 0)
            return 1;
        // Check if value is above range (greater than max)
        if (range.Max.CompareTo(value) < 0)
            return -1;
        // Value is within range.
        return 0;
    }
}
static void Main(string[] args)
{
    var ranges = new Range<int>[]
    {
        new Range<int>(1, 10000),
        new Range<int>(10001, 40000),
        new Range<int>(40001, int.MaxValue),
    };
    var rangeComparer = new RangeComparer<int>();
    Console.WriteLine(BinarySearch(ranges, 7, rangeComparer));       // gives 0
    Console.WriteLine(BinarySearch(ranges, 10007, rangeComparer));   // gives 1
    Console.WriteLine(BinarySearch(ranges, 40007, rangeComparer));   // gives 2
    Console.WriteLine(BinarySearch(ranges, 1, rangeComparer));       // gives 0
    Console.WriteLine(BinarySearch(ranges, 10000, rangeComparer));   // gives 0
    Console.WriteLine(BinarySearch(ranges, 40000, rangeComparer));   // gives 1
    Console.WriteLine(BinarySearch(ranges, 40001, rangeComparer));   // gives 2
}

别忘了：

  • 范围必须按升序排列
  • 范围不能重叠
  • BinarySearch返回的索引为零
相关文章：