How to perform a binary search on IList<T>?

37

7

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.

Daniel Brückner

Posted 2009-06-08T21:09:09.183

Reputation: 50 211

1This looks like an oversight, it's a shame .NET makes you reinvent the wheel. We should report the bug to Microsoft. – Colonel Panic – 2015-08-03T15:31:55.640

2You can't perform a binary search on any old data - it has to have been appropriately sorted and without duplicates first – Jeff Yates – 2009-06-08T21:15:43.460

1You can assume that the list is sorted. – Daniel Brückner – 2009-06-08T21:19:45.340

Do you know the underlying type of the object? List<T> does provide the Sort and BinarySearch methods. – Peter Ruderman – 2009-06-08T21:21:56.740

That's the problem ... I don't know anything about the implementation and don't want to put assumptions on it. – Daniel Brückner – 2009-06-08T21:24:52.443

1But 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 – 2009-06-08T21:26:50.693

2Yes, 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. – Daniel Brückner – 2009-06-08T21:34:26.620

Answers

31

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.

Lasse Vågsæther Karlsen

Posted 2009-06-08T21:09:09.183

Reputation: 284 844

1Hot dang! That search is fast – Dr. ABT – 2012-04-03T21:12:46.067

1Late 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. – Lasse Vågsæther Karlsen – 2009-09-28T12:47:53.863

List<T> has a BinarySearch method with a slightly different contract. Be aware that this method does not match that method. – John Gietzen – 2013-10-17T02:07:41.203

9

By returning ~lower instead of -1 when item is not found, the behavior will be equal to that of Array.BinarySearch, see http://stackoverflow.com/a/2948872/167251 also.

– larsmoa – 2013-11-27T13:05:14.600

Does IList<T> have a Count method? I don't see it in the docs. – Peter Ruderman – 2009-06-08T21:26:42.923

1

IList<T> has a Count property http://msdn.microsoft.com/en-us/library/s16t9z9d.aspx

– Bryce Kahle – 2009-06-08T21:30:43.103

Properties are at the bottom of the page. – Meta-Knight – 2009-06-08T21:33:11.897

2IList<T> by itself does not have a Count property, but it requires ICollection<T> to be implemented, which does. – Lasse Vågsæther Karlsen – 2009-06-08T21:37:14.930

It's inherited from ICollection<T> (which makes sense), but my version of MSDN doesn't show inherited properties and methods (which doesn't make so much sense). ;) – Peter Ruderman – 2009-06-08T21:37:57.673

You can turn showing inherited members on and off. – Daniel Brückner – 2009-06-08T21:40:45.487

2You 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 – 2009-07-22T15:43:30.790

30

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

devgeezer

Posted 2009-06-08T21:09:09.183

Reputation: 3 024

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? – rocketsarefast – 2013-04-11T23:01:09.380

@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 – 2013-12-12T19:58:54.203

1That'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. – Shalom Craimer – 2011-02-01T09:07:45.400

5That's exactly why I wanted to use a build-in implementation - it's quite hard to get Binary Search right. +1 – Daniel Brückner – 2009-06-09T12:39:13.267

28

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

Antoine Aubry

Posted 2009-06-08T21:09:09.183

Reputation: 6 687

1I checked out the implementation in .NET 4.0 and found that they do indeed use ~lower. See my answer for a working implementation. – angularsen – 2012-01-01T15:41:41.767

Ok, I checked again and you are indeed correct. I have updated the answer to return ~lower. Thanks – Antoine Aubry – 2012-01-03T10:28:22.627

1When I've written binary-search code, I've often included a "bias" option so that the "compare equal" case will be forced one way or the other; that has the effect of allowing the caller to specify whether to return the first or last matching item in the event that there are multiple matches. – supercat – 2013-04-08T21:06:49.810

1

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&lt;K, V&gt; and I have used your code for that

– Eugene Beresovsky – 2015-07-17T00:00:31.083

Very useable, thank you. I did'nt copy the comments, because why would I comment that the BinarySearch extension does a binary search? I also replaced TItem just with T and TSearch with TKey. – Gerard – 2018-03-26T10:05:39.293

Really, you have no idea how often I need to copy this code (because it behaves like the built-in .Net one). – Jonathan Dickinson – 2011-10-05T16:22:18.497

1

If you want, you can use the BinarySearchExtensions class from the SixPack library.

– Antoine Aubry – 2011-10-06T17:33:34.160

1Naaw, I am just applauding you for keeping it consistent with the BCL. This is honestly the correct answer. – Jonathan Dickinson – 2011-10-06T18:32:56.457

2

Are you sure ~lower should be returned and not ~upper? Inserting at lower will break the order if I am not mistaken. http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx

– angularsen – 2011-11-03T13:22:28.427

Originally, I was returning ~middle. Then @mid commented that i should be returning ~lower instead because he claimed that the implementation of ArraySortHelper.InternalBinarySearch did that. Now I have checked the implementation of ArraySortHelper.InternalBinarySearch and it returns ~middle. So, what is the correct result? – Antoine Aubry – 2011-11-07T14:44:30.503

4

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.

angularsen

Posted 2009-06-08T21:09:09.183

Reputation: 5 418

You seemed to have missed Antoine's answer. It has been there since 2010 and makes your answer redundant.

– Eugene Beresovsky – 2015-07-17T00:42:17.133

1And 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 – 2015-07-17T01:14:15.353

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). – Eugene Beresovsky – 2015-07-17T01:31:05.107

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>.

Andrew Hare

Posted 2009-06-08T21:09:09.183

Reputation: 272 497

1One 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. – rocketsarefast – 2013-04-11T22:49:17.243

You can assume that the list is sorted. But I assume there is indeed the same problem with sort - how to sort IList<T>? – Daniel Brückner – 2009-06-08T21:19:30.677

Copying is absolutly no option because it's O(n) so binary search will not make much sense after that... ;) – Daniel Brückner – 2009-06-08T21:23:17.190

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. – Bryce Kahle – 2009-06-08T21:46:58.063

Of course, you can sort IList<T>, but there seems to be no build-in support, too. – Daniel Brückner – 2009-06-08T23:00:21.410

To sort an IList<T> you can use the sort linq extension method. – Rune FS – 2009-06-09T08:48:04.323

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.

mdi

Posted 2009-06-08T21:09:09.183

Reputation: 430

1Thanks 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. – Antoine Aubry – 2010-08-05T16:00:09.173

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>
{
    // ...
}

Christian

Posted 2009-06-08T21:09:09.183

Reputation: 6 790

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.

Pratik Bhattacharya

Posted 2009-06-08T21:09:09.183

Reputation: 1 813

-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.

Anonymous

Posted 2009-06-08T21:09:09.183

Reputation: 7

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

-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.

Nathan

Posted 2009-06-08T21:09:09.183

Reputation: 6 336

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 http://stackoverflow.com/a/967081/24954 Editing answer to make this more clear.

– Nathan – 2013-12-12T16:53:19.260

5ToList() 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. – Daniel Brückner – 2009-06-08T21:55:45.797

-2

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

Joel Coehoorn

Posted 2009-06-08T21:09:09.183

Reputation: 304 185

3and sortedlist doesn't. – nawfal – 2014-06-13T06:53:46.240

4List<T> has a BinarySearch() method. – Daniel Brückner – 2009-06-08T21:36:35.960