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?
2 Answers
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);
}
Comments
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?
2 Comments
Robert Harvey
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).
Dustin Kingen
@RobertHarvey I forgot about the binary search part let me modify my answer.
Arrayimplementation of a binary search.Array.BinarySearchwill 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.