C # binary search using delegation condition

Question

I have a List<T> that I want to search not for a given element, but for an element that satisfies a given condition. Given the item in the list, I can check which of the 4 conditions is true:

• the desired item should be on the left
• the desired item should be on the right
• this is the desired item
• desired may not be on the list

A quick look at the list functions was not encouraging, so I wonder if anyone knows of a function that I can use?

Edit: this is a local list so that I know that it will be sorted correctly.

Edit: BinarySearch looks almost correct, but in my case I don't have an element to compare. I would use Jon Skeet's solution and ignore one argument, but I'm not sure I can expect it to always be the same argument.

Answer 1

New edit: I will leave additional binary searches below, as they will be useful for others, and here is the final version, which I think you really want. Your delegate should return a positive number if the item he is looking for is “less than” the specified, a negative number if it is “greater than what is specified,” and 0 if it is correct.

 public static int BinarySearchForMatch<T>(this IList<T> list, Func<T,int> comparer) { int min = 0; int max = list.Count-1; while (min <= max) { int mid = (min + max) / 2; int comparison = comparer(list[mid]); if (comparison == 0) { return mid; } if (comparison < 0) { min = mid+1; } else { max = mid-1; } } return ~min; } 

Old edit: I will leave the original answer below, but here are two more options.

The first takes a projection from the source data into the key type and defines the key to search. The comparison itself is performed by default for this type of key:

 public static int BinarySearchBy<TSource,TKey>(this IList<TSource> list, Func<TSource,TKey> projection, TKey key) { int min = 0; int max = list.Count-1; while (min <= max) { int mid = (min + max) / 2; TKey midKey = projection(list[mid]); int comparison = Comparer<TKey>.Default.Compare(midKey, key); if (comparison == 0) { return mid; } if (comparison < 0) { min = mid+1; } else { max = mid-1; } } return ~min; } 

The second uses Func instead to compare the item from the list with the key we are looking for. Of course, the code is almost the same as the comparison:

 public static int BinarySearchBy<TSource,TKey>(this IList<TSource> list, Func<TSource,TKey,int> comparer, TKey key) { int min = 0; int max = list.Count-1; while (min <= max) { int mid = (min + max) / 2; int comparison = comparer(list[mid], key); if (comparison == 0) { return mid; } if (comparison < 0) { min = mid+1; } else { max = mid-1; } } return ~min; } 

They are both untested, but at least compile :)

Original answer:

You can use List<T>.BinarySearch with IComparer<T> . You do not need to write your own implementation of IComparer<T> - I got in MiscUtil , which builds IComparer<T> from a Comparison<T> delegate. These are only spots of the first three conditions, but the binary search will work the last of the rest.

Actually the code is so short that I could also paste it here (no comment).

 public sealed class ComparisonComparer<T> : IComparer<T> { readonly Comparison<T> comparison; public ComparisonComparer(Comparison<T> comparison) { if (comparison == null) { throw new ArgumentNullException("comparison"); } this.comparison = comparison; } public int Compare(T x, T y) { return comparison(x, y); } } 

So you can do something like:

 var comparer = new ComparisonComparer<Person>((p1, p2) => p1.ID.CompareTo(p2.ID)); int index = list.BinarySearch(employee, comparer); 

MiscUtil also has a ProjectionComparer , you might be interested - you just specify the projection, as in OrderBy with LINQ, but it really depends on your use case.

Answer 2

Are you sure about these conditions? This usually works if the list is sorted, in which case, perhaps you want to use SortedList<TKey, TValue> .

In any case, assuming C # 3.0 or later, you probably want to use the .Where() method. Write in your state, like a lambda, and let the frame search. He should use the search method that matches the collection.

Answer 3

You might want to implement it in a custom comparator for your object (strangely called a comparator in C # docs).