Binary multi search

Question

I want to get all the position of (8) in a array like this: (3,5,6,7,8,8,9,33,34,45). But my code returns only one position and forget the second one:

This is my binary search code:

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

What you want is the same as the C++ "equal_range()" method.

If you look at the standard C++ implementations, they use "lower_bound()" to find the low value and "upper_bound" to find the high value. It does it like this rather than doing a "scan" from the index found from a normal binary search to ensure that it always works within an O(Log(N)) timescale. A linear search for the bounds could degenerate into an O(Log(N)) operation followed by an O(N) one.

Here's a C# implementation of C++'s lower_bound(), upper_bound() and equal_range():

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

(Note: This code uses the old Tuple<> class to return the ranges. If you're using a recent version of C# and .Net, you could change this to return proper tuples like public static (int LowerBound, int UpperBound) EqualRange<T>(...)).

Answer 2

As Matt implied in the comments, you could return an IEnumerable<int>, yield returning the values:

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

You would use this as follows:

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

Or materialize an array or list if you want to do that up front:

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

You're returning an int. That's only one position. You may need to change your code to return an array: int[] also Where you do return middle; you should do a search of ALL matching values before and after middle. This could be a linear search to keep it simple, or it could be binary-ish if you expect potentially lots of matching values.