二分多重搜索

Question

我想要得到(8)的所有位置，像这样的数组：(3，5，6，7，8，8，8，9，33，34，45)。但是我的代码只返回一个位置，而忘记了第二个位置：

这是我的二进制搜索代码：

private static int BinarySearch(int[] array, int item)
{
    int left = 0;
    int right = array.Length - 1;

    while (left <= right)
    {
        var middle = (left + right) / 2;

        if (array[middle] == item)
            return middle;

        if (item < array[middle])
            right = middle - 1;
        else
            left = middle + 1;
    }

    return -1;
}

Answer 1

你想要的和C++ "equal_range()" method是一样的。

看看标准的C++实现，它们使用"lower_bound()“查找低值，使用"upper_bound”查找高值。它是这样做的，而不是对从普通二进制搜索中找到的索引进行“扫描”，以确保它始终在O(Log(N))时间刻度内工作。对边界的线性搜索可能退化为O(Log(N))操作，然后是O(N)操作。

下面是C++的lower_bound()、upper_bound()和equal_range()的C#实现

public static class BoundedSearch
{
    /// <summary>Same as C++'s equal_range()</summary>

    public static Tuple<int, int> EqualRange<T>(IList<T> values, T target) where T : IComparable<T>
    {
        int lowerBound = LowerBound(values, target, 0, values.Count);
        int upperBound = UpperBound(values, target, lowerBound, values.Count);

        return new Tuple<int, int>(lowerBound, upperBound);
    }

    /// <summary>Same as C++'s lower_bound()</summary>

    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;
    }

    /// <summary>Same as C++'s upper_bound()</summary>

    public static int UpperBound<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)
                right = mid;
            else
                left = mid + 1;
        }

        return left;
    }
}       

(注意:此代码使用旧的Tuple<>类返回范围。如果您使用的是最新版本的C#和.Net，则可以将其更改为返回适当的元组(如public static (int LowerBound, int UpperBound) EqualRange<T>(...))。

Answer 2

正如马特在评论中暗示的那样，你可以返回一个IEnumerable<int>，返回以下值：

private static IEnumerable<int> BinarySearch(int[] array, int item)
{
    int left = 0;
    int right = array.Length - 1;

    while (left <= right)
    {
        if (array[left] == item)
            yield return left;

        if (left == right)
            break;

        if (array[right] == item)
            yield return right;

        left++;
        right--;
    }
}

您可以按如下方式使用它：

static void Main(string[] args)
{
    var items = new int[] { 3, 5, 6, 7, 8, 8, 9, 33, 34, 45, 8 };

    foreach (var item in BinarySearch(items, 8))
    {
        Console.WriteLine(item);
    }
}

或者物化一个数组或列表，如果你想这样做的话：

static void Main(string[] args)
{
    var items = new int[] { 3, 5, 6, 7, 8, 8, 9, 33, 34, 45, 8 };

    var results = BinarySearch(items, 8).ToArray();
}

Answer 3

您将返回一个int。这只是一个位置。您可能需要更改代码以返回一个数组：int[]，也可以在其中执行return middle；您应该在middle之前和之后搜索所有匹配值。这可以是一个线性搜索，以保持它的简单性，或者如果您希望有大量的匹配值，它也可以是二进制的。