48

Simple question - given an IList<T> how do you perform a binary search without writing the method yourself and without copying the data to a type with build-in binary search support. My current status is the following.

  • List<T>.BinarySearch() is not a member of IList<T>
  • There is no equivalent of the ArrayList.Adapter() method for List<T>
  • IList<T> does not inherit from IList, hence using ArrayList.Adapter() is not possible

I tend to believe that is not possible with build-in methods, but I cannot believe that such a basic method is missing from the BCL/FCL.

If it is not possible, who can give the shortest, fastest, smartest, or most beatiful binary search implementation for IList<T>?

UPDATE

We all know that a list must be sorted before using binary search, hence you can assume that it is. But I assume (but did not verify) it is the same problem with sort - how do you sort IList<T>?

CONCLUSION

There seems to be no build-in binary search for IList<T>. One can use First() and OrderBy() LINQ methods to search and sort, but it will likly have a performance hit. Implementing it yourself (as an extension method) seems the best you can do.

8
  • 2
    You can't perform a binary search on any old data - it has to have been appropriately sorted and without duplicates first
    – Jeff Yates
    Jun 8, 2009 at 21:15
  • 2
    You can assume that the list is sorted. Jun 8, 2009 at 21:19
  • 1
    But you just said we can assume it is sorted. So you don't want to put assumptions on it except that it is sorted and will support a binary search?
    – Jeff Yates
    Jun 8, 2009 at 21:26
  • 3
    Yes, it's a sorted IList<T> and I want to search it. I can write a binary search myself in a minute or two, but I would really like to see a build-in method. Jun 8, 2009 at 21:34
  • 1
    This looks like an oversight, it's a shame .NET makes you reinvent the wheel. We should report the bug to Microsoft. Aug 3, 2015 at 15:31

11 Answers 11

43

I doubt there is a general purpose binary search method in .NET like that, except for the one being present in some base classes (but apparently not in the interfaces), so here's my general purpose one.

public static Int32 BinarySearchIndexOf<T>(this IList<T> list, T value, IComparer<T> comparer = null)
{
    if (list == null)
        throw new ArgumentNullException(nameof(list));

    comparer = comparer ?? Comparer<T>.Default;

    Int32 lower = 0;
    Int32 upper = list.Count - 1;

    while (lower <= upper)
    {
        Int32 middle = lower + (upper - lower) / 2;
        Int32 comparisonResult = comparer.Compare(value, list[middle]);
        if (comparisonResult == 0)
            return middle;
        else if (comparisonResult < 0)
            upper = middle - 1;
        else
            lower = middle + 1;
    }

    return ~lower;
}

This of course assumes that the list in question is already sorted, according to the same rules that the comparer will use.

8
  • 1
    IList<T> has a Count property msdn.microsoft.com/en-us/library/s16t9z9d.aspx Jun 8, 2009 at 21:30
  • 2
    IList<T> by itself does not have a Count property, but it requires ICollection<T> to be implemented, which does. Jun 8, 2009 at 21:37
  • 2
    You don't need to call ReferenceEquals for the parameter validation. Since operator overloads are resolved at compile time, == will ignore any overloads on the actual types of the parameters, and the interfaces cannot override the operators.
    – SLaks
    Jul 22, 2009 at 15:43
  • 1
    Late comment, but whatever. I know I don't have to use ReferenceEquals, but those lines there are from snippets I use, so I tend to use ReferenceEquals every time, even when I don't have to. Sep 28, 2009 at 12:47
  • 11
    By returning ~lower instead of -1 when item is not found, the behavior will be equal to that of Array.BinarySearch, see stackoverflow.com/a/2948872/167251 also.
    – larsmoa
    Nov 27, 2013 at 13:05
37

Here's my version of Lasse's code. I find it useful to be able to use a lambda expression to perform the search. When searching in a list of objects, it permits to pass only the key that was used to sort. Implementations that use IComparer are trivially derived from this one.

I also like to return ~lower when no match is found. Array.BinarySearch does it and it allows you to know where the item you searched for should be inserted in order to keep the ordering.

/// <summary>
/// Performs a binary search on the specified collection.
/// </summary>
/// <typeparam name="TItem">The type of the item.</typeparam>
/// <typeparam name="TSearch">The type of the searched item.</typeparam>
/// <param name="list">The list to be searched.</param>
/// <param name="value">The value to search for.</param>
/// <param name="comparer">The comparer that is used to compare the value
/// with the list items.</param>
/// <returns></returns>
public static int BinarySearch<TItem, TSearch>(this IList<TItem> list,
    TSearch value, Func<TSearch, TItem, int> comparer)
{
    if (list == null)
    {
        throw new ArgumentNullException("list");
    }
    if (comparer == null)
    {
        throw new ArgumentNullException("comparer");
    }

    int lower = 0;
    int upper = list.Count - 1;

    while (lower <= upper)
    {
        int middle = lower + (upper - lower) / 2;
        int comparisonResult = comparer(value, list[middle]);
        if (comparisonResult < 0)
        {
            upper = middle - 1;
        }
        else if (comparisonResult > 0)
        {
            lower = middle + 1;
        }
        else
        {
            return middle;
        }
    }

    return ~lower;
}

/// <summary>
/// Performs a binary search on the specified collection.
/// </summary>
/// <typeparam name="TItem">The type of the item.</typeparam>
/// <param name="list">The list to be searched.</param>
/// <param name="value">The value to search for.</param>
/// <returns></returns>
public static int BinarySearch<TItem>(this IList<TItem> list, TItem value)
{
    return BinarySearch(list, value, Comparer<TItem>.Default);
}

/// <summary>
/// Performs a binary search on the specified collection.
/// </summary>
/// <typeparam name="TItem">The type of the item.</typeparam>
/// <param name="list">The list to be searched.</param>
/// <param name="value">The value to search for.</param>
/// <param name="comparer">The comparer that is used to compare the value
/// with the list items.</param>
/// <returns></returns>
public static int BinarySearch<TItem>(this IList<TItem> list, TItem value,
    IComparer<TItem> comparer)
{
    return list.BinarySearch(value, comparer.Compare);
}
10
  • 1
    If you want, you can use the BinarySearchExtensions class from the SixPack library. Oct 6, 2011 at 17:33
  • 1
    Naaw, I am just applauding you for keeping it consistent with the BCL. This is honestly the correct answer. Oct 6, 2011 at 18:32
  • 2
    Are you sure ~lower should be returned and not ~upper? Inserting at lower will break the order if I am not mistaken. msdn.microsoft.com/en-us/library/w4e7fxsh.aspx
    – angularsen
    Nov 3, 2011 at 13:22
  • 1
    I checked out the implementation in .NET 4.0 and found that they do indeed use ~lower. See my answer for a working implementation.
    – angularsen
    Jan 1, 2012 at 15:41
  • 2
    Thanks for this copy-and-pastable solution. The ~lower (instead of a constant -1) is crucial when implementing many interesting features on sorted lists like TailMap and HeadMap on SortedList<K, V> and I have used your code for that Jul 17, 2015 at 0:00
34

I like the solution with the extension method. However, a bit of warning is in order.

This is effectively Jon Bentley's implementation from his book Programming Pearls and it suffers modestly from a bug with numeric overflow that went undiscovered for 20 years or so. The (upper+lower) can overflow Int32 if you have a large number of items in the IList. A resolution to this is to do the middle calculation a bit differently using a subtraction instead; Middle = Lower + (Upper - Lower) / 2;

Bentley also warned in Programming Pearls that while the binary search algorithm was published in 1946 and the first correct implementation wasn't published until 1962.

http://en.wikipedia.org/wiki/Binary_search#Numerical_difficulties

4
  • 9
    That's exactly why I wanted to use a build-in implementation - it's quite hard to get Binary Search right. +1 Jun 9, 2009 at 12:39
  • 1
    That's a great point! Personally, I don't think I'd be using a binary search to look through a collection that is larger than 2^30 items. Of course, if a programmer's collections really are that large and entirely loaded into RAM, I feel that he's already failed to pay attention to what he's asking his computer to do. Feb 1, 2011 at 9:07
  • really scraimer? you think using more than 4GB of ram is ridiculous? Are you going to be available in 30 years to tell us 4TB of ram is ridiculous? Apr 11, 2013 at 23:01
  • @rocketsarefast: In general, it is useful to have data structures divided into layers, where no particular layer is overly large. If the number of bytes in a data item is many millions of times the number of items, that suggests that perhaps it may be better to subdivide the item. If the number of items exceeds the size of each item by a factor of many millions, it may be better to aggregate the items into larger chunks. For a collection which takes a total of 1TB of RAM to have over two billion items, or items bigger than two gig each, would require a 4,000,000:1 item/size ratio.
    – supercat
    Dec 12, 2013 at 19:58
7

I have been struggling with getting this right for some time now. In particular the return values for edge cases as specified in MSDN: http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx

I have now copied the ArraySortHelper.InternalBinarySearch() from .NET 4.0 and made my own flavor for various reasons.

Usage:

var numbers = new List<int>() { ... };
var items = new List<FooInt>() { ... };

int result1 = numbers.BinarySearchIndexOf(5);
int result2 = items.BinarySearchIndexOfBy(foo => foo.bar, 5);

This should work with all .NET types. I have tried int, long and double so far.

Implementation:

public static class BinarySearchUtils
{
    public static int BinarySearchIndexOf<TItem>(this IList<TItem> list,
        TItem targetValue, IComparer<TItem> comparer = null)
    {
        Func<TItem, TItem, int> compareFunc =
            comparer != null ? comparer.Compare :
            (Func<TItem, TItem, int>) Comparer<TItem>.Default.Compare;
        int index = BinarySearchIndexOfBy(list, compareFunc, targetValue);
        return index;
    }

    public static int BinarySearchIndexOfBy<TItem, TValue>(this IList<TItem> list,
        Func<TItem, TValue, int> comparer, TValue value)
    {
        if (list == null)
            throw new ArgumentNullException("list");

        if (comparer == null)
            throw new ArgumentNullException("comparer");

        if (list.Count == 0)
            return -1;

        // Implementation below copied largely from .NET4
        // ArraySortHelper.InternalBinarySearch()
        int lo = 0;
        int hi = list.Count - 1;
        while (lo <= hi)
        {
            int i = lo + ((hi - lo) >> 1);
            int order = comparer(list[i], value);

            if (order == 0)
                return i;
            if (order < 0)
            {
                lo = i + 1;
            }
            else
            {
                hi = i - 1;
            }
        }

        return ~lo;
    }
}

Unit tests:

[TestFixture]
public class BinarySearchUtilsTest
{
    [Test]
    public void BinarySearchReturnValueByMsdnSpecification()
    {
        var numbers = new List<int>() { 1, 3 };

        // Following the MSDN documentation for List<T>.BinarySearch:
        // http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx

        // The zero-based index of item in the sorted List(Of T), if item is found;
        int index = numbers.BinarySearchIndexOf(1);
        Assert.AreEqual(0, index);

        index = numbers.BinarySearchIndexOf(3);
        Assert.AreEqual(1, index);


        // otherwise, a negative number that is the bitwise complement of the
        // index of the next element that is larger than item
        index = numbers.BinarySearchIndexOf(0);
        Assert.AreEqual(~0, index);

        index = numbers.BinarySearchIndexOf(2);
        Assert.AreEqual(~1, index);


        // or, if there is no larger element, the bitwise complement of Count.
        index = numbers.BinarySearchIndexOf(4);
        Assert.AreEqual(~numbers.Count, index);
    }
}

I just scissored this out from my own code, so please comment if it doesn't work out of the box.

Hope this settles the issue with a working implementation once and for all, at least according to MSDN specs.

3
  • You seemed to have missed Antoine's answer. It has been there since 2010 and makes your answer redundant. Jul 17, 2015 at 0:42
  • 1
    And you missed my comments on his answer. I believe I found a flaw in the implementation, at least per MSDN specs. Please correct me if I am wrong.
    – angularsen
    Jul 17, 2015 at 1:14
  • You are right. Well, it's redundant now since Antoine has fixed it after your comments (and indeed after your answer). I just upvoted your answer. You might however consider adding a comment as to why your seemingly redundant answer exists as a preamble to it (which currently is a general comment only on corner cases, not mentioning the previous problem with Antoine's answer that prompted yours). Jul 17, 2015 at 1:31
4

You are going to have a couple of problems binary-searching an IList<T>, First ,like you mentioned, the BinarySearch method on the List<T> is not a member of the IList<T> interface. Second, you have no way of sorting the list prior to searching (which you must do for a binary search to work).

I think your best bet is to create a new List<T>, sort it, and then search. It's not perfect but you don't have to many options if you have an IList<T>.

7
  • You can assume that the list is sorted. But I assume there is indeed the same problem with sort - how to sort IList<T>? Jun 8, 2009 at 21:19
  • 1
    Copying is absolutly no option because it's O(n) so binary search will not make much sense after that... ;) Jun 8, 2009 at 21:23
  • Why would there be no way of sorting? IList<T> allows random access, so as long as you have the ability to compare objects of type T, then you could sort it beforehand. Jun 8, 2009 at 21:46
  • Of course, you can sort IList<T>, but there seems to be no build-in support, too. Jun 8, 2009 at 23:00
  • 4
    One common way to get a sorted IList<T> is by using a SortedList. Then you try to binary search the keys, to find there is no way. I would guess many people reading this thread are frustrated by the lack of binarysearch on SortedList. Apr 11, 2013 at 22:49
3

Note that there is a bug in the implementation provided by Antoine below: when searching for an item greater than any in the list. The return value should be ~lower not ~middle. Decompile method ArraySortHelper.InternalBinarySearch (mscorlib) to see the framework implementation.

1
  • 1
    Thanks for finding this issue. Binary search is definitely tough to get right! Instead of replying to the question, you should comment on the answer, that makes it easier to find the related post. Aug 5, 2010 at 16:00
2

If you need a ready-made implementation for binary search on IList<T>s, Wintellect's Power Collections has one (in Algorithms.cs):

/// <summary>
/// Searches a sorted list for an item via binary search. The list must be sorted
/// by the natural ordering of the type (it's implementation of IComparable&lt;T&gt;).
/// </summary>
/// <param name="list">The sorted list to search.</param>
/// <param name="item">The item to search for.</param>
/// <param name="index">Returns the first index at which the item can be found. If the return
/// value is zero, indicating that <paramref name="item"/> was not present in the list, then this
/// returns the index at which <paramref name="item"/> could be inserted to maintain the sorted
/// order of the list.</param>
/// <returns>The number of items equal to <paramref name="item"/> that appear in the list.</returns>
public static int BinarySearch<T>(IList<T> list, T item, out int index)
        where T: IComparable<T>
{
    // ...
}
2

You can use List<T>.BinarySearch(T item). If you want to use a custom comparer then use List<T>.BinarySearch(T item, IComparer<T> comparer). Take a look at this MSDN link for more details.

-1

Keep in mind that binary search can be quite inefficient for some list implementations. For example, for a linked list it is O(n) if you implement it correctly, and O(n log n) if you implement it naively.

1
  • 1
    Although a useful statement in the context of lists in general, I assume you have been downvoted because the question is about IList<T>, which is supposed to provide O(1) access by index. At least .Net's own LinkedList<T> does not implement IList<T> - and I'm sure it's for that very reason. Although of course anyone can implement their O(n) version of IList<T>.Item[index] if they so choose. Jul 17, 2015 at 0:49
-1

If you can use .NET 3.5, you can use the build in Linq extension methods:

using System.Linq;

IList<string> ls = ...;
var orderedList = ls.OrderBy(x => x).ToList();
orderedList.BinarySearch(...);

However, this is really just a slightly different way of going about Andrew Hare's solution, and is only really helpful if you are searching multiple times off of the same ordered list.

2
  • 8
    ToList() will copy all items into a new List<T>. Then you just use List<T>.BinarySearch(). Because copying is O(n) it's no option in combination with binary search. Jun 8, 2009 at 21:55
  • 1
    If this is just a one-off call, then yes, that is true. However, if you store the ordered list, and do multiple binary searches off of that, then the O(n) is a one-time hit. Which is exactly the same performance you get with stackoverflow.com/a/967081/24954 Editing answer to make this more clear.
    – Nathan
    Dec 12, 2013 at 16:53
-3

Note that while List and IList do not have a BinarySearch method, SortedList does.

2
  • 4
    List<T> has a BinarySearch() method. Jun 8, 2009 at 21:36
  • 4
    and sortedlist doesn't.
    – nawfal
    Jun 13, 2014 at 6:53

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.