Binary searching array of custom type

Question

I have an array A of objects, each with the public field Value (double) which have random doubles between 0 and 1. A is sorted by this field. I create double random = 0.25. Now I want to find the first object from A with A[index].Value >= random. Can I do this with int index = Array.BinarySearch() in some way?

Aeronautics

Sounds like since you want the first item of an imprecise match, the most a binary searching algorithm could do is isolate a "small enough" range for you to iterate over, but I could be mistaken. – Tarpley

@AnthonyPegram You are mistaken, a binary search is exactly what he wants, the problem is that he doesnt' have an object of the same type as the array, he just has the value he wants to compare on. Logically, a binary search can work, he just may not be able to use the Array implementation of a binary search. – Pratfall

@Servy, you could be correct, I'm thinking it through in my head here. He would have to keep searching after finding that initial match (even if exact) until he has satisfied whether or not he has found the sequential first occurence of the match. I was thinking a typical binary search would happily return once any match was found. (I note that I am woefully incompetent in the realm of algorithms, having not been a CS major or otherwise filled in those gaps.) – Tarpley

@AnthonyPegram Array.BinarySearch will return an index if it found an exact match, and the bitwise compliment of the index where the given item belongs if there was no match, so from the result you already know if it found an exact match or not. If there was an exact match, you may indeed need to add a bit of special handling to support duplicate items in the array. – Pratfall

Answer 1

Here is an implementation of BinarySearch that you can use. In addition to the other arguments that would normally be accepted, it also accepts a selector which determines the actual object that should be compared for each item, and for the value to find it accepts a value of that type, rather than the type of the array.

public static int BinarySearch<TSource, TKey>(this IList<TSource> collection
    , TKey item, Func<TSource, TKey> selector, Comparer<TKey> comparer = null)
{
    return BinarySearch(collection, item, selector, comparer, 0, collection.Count);
}
private static int BinarySearch<TSource, TKey>(this IList<TSource> collection
    , TKey item, Func<TSource, TKey> selector, Comparer<TKey> comparer
    , int startIndex, int endIndex)
{
    comparer = comparer ?? Comparer<TKey>.Default;

    while (true)
    {
        if (startIndex == endIndex)
        {
            return startIndex;
        }

        int testIndex = startIndex + ((endIndex - startIndex) / 2);
        int comparision = comparer.Compare(selector(collection[testIndex]), item);
        if (comparision > 0)
        {
            endIndex = testIndex;
        }
        else if (comparision == 0)
        {
            return testIndex;
        }
        else
        {
            startIndex = testIndex + 1;
        }
    }
}

To use it is simple enough:

public class Foo
{
    public double Value { get; set; }
}

private static void Main(string[] args)
{
    Foo[] array = new Foo[5];
    //populate array with values
    array.BinarySearch(.25, item => item.Value);
}

Pratfall

Answer 2

Best way would be to roll your own.

public static class ListExtensions
{
        public static T BinarySearchFirst<T>(this IList<T> list, Func<T, int> predicate)
            where T : IComparable<T>
    {
        int min = 0;
        int max = list.Count;
        while (min < max)
        {
            int mid = (max + min) / 2;
            T midItem = list[mid];
            int comp = predicate(midItem);
            if (comp < 0)
            {
                min = mid + 1;
            }
            else if (comp > 0)
            {
                max = mid - 1;
            }
            else
            {
                return midItem;
            }
        }
        if (min == max &&
            predicate(list[min]) == 0)
        {
            return list[min];
        }
        throw new InvalidOperationException("Item not found");
    }
}

Usage:

var list = Enumerable.Range(1, 25).ToList();
var mid = list.Count / 2; //13

list.BinarySearchFirst(c => c >= 23 ? 0 : -1); // 23

Based on Can LINQ use binary search when the collection is ordered?

Shumpert

Assuming he really wants to search linearly, starting with the first item in the array. The Binary Search thing leads me to believe he wants to get the answer faster than O(n). – Doable

@RobertHarvey I forgot about the binary search part let me modify my answer. – Shumpert