CODEWITHSUNDEEP
c#.netlist
Leo Vo
Leo Vo

Reputation: 10330

Find quickly index of item in sorted list

I have a object:

public class MyObject
{
int id;
string value;
}

I also have a list:

List<MyObject> list = new List<MyObject>;
for(int i=0;i;i<100000;i++)
{
list.Add(new MyObject(i, string.Format("Item {0}", i));
}

And list will be:

1, "Item 1"
2, "Item 2"
....
99999, "Item 99999"

This list is a sorted list which sorted on ID field. Note this is an example to describe a sorted list, it is not simple like the above example.

I want to find a item of ordered list based on ID field. I don't know .NET Framework has support quickly search on a ordered list without enumerating.

I am interested in performance because of a big list. Thanks.

Best regards.

Upvotes: 1

Views: 9418

Answers (8)

The Lonely Coder
The Lonely Coder

Reputation: 633

For those people who have come across this question based on it's title (Find quickly index of item in sorted list) you may be interested to know that SortedList< TKey, TValue> has the following two methods:-

    public int IndexOfKey(TKey key);
    public int IndexOfValue(TValue value);

and SortedList has:-

    public virtual int IndexOfKey(object key);
    public virtual int IndexOfValue(object value);

Upvotes: 0

LukeH
LukeH

Reputation: 269498

You can use a binary search for this.

You can use the built-in implementation, providing a custom IComparer<T> that compares on your type's id property:

var objToFind = new MyObject { id = 42 };

int foundIndex = yourList.BinarySearch(objToFind, new MyObjectIdComparer());

// ...

public class MyObjectIdComparer : Comparer<MyObject>
{
    public override int Compare(MyObject x, MyObject y)
    {
        // argument checking etc removed for brevity

        return x.id.CompareTo(y.id);
    }
}

Upvotes: 8

BigMike
BigMike

Reputation: 6873

Take a look at Linq

using System.Linq;

Obtain a queryable from your list (usually via .AsQueryable() call)

Apply a .Select() on obtained Queryable

var c = queryable.Select (x => x.field == 999)

Upvotes: 0

user586399
user586399

Reputation:

The index regarding you ID is ID - 1. However, if you have deleted items, that way will no work. You can then use Binary search, PROVIDED that you list is sorted. So you have to keep it always sorted, or you will use uneffecient Linear search.

Upvotes: 0

Jon Skeet
Jon Skeet

Reputation: 1502336

Four options:

  • If your list will always contain items with ID 1...n, then you can just do:

    MyObject foo = list[id - 1];

  • You could populate a Dictionary<int, MyObject>

  • You could make MyObject implement IComparable<T> or IComparable (ordering by ID) and use List<T>.BinarySearch, providing a dummy MyObject with the desired ID
  • You could implement binary searching yourself - it's not terribly hard to do so

Note that if you take the last approach, you may want to do so in a generic way as an extension method so that you can reuse it later:

// Optionally another overload with an IComparer<TKey>
public static TItem ProjectedBinarySearch<TItem, TKey>(
    this IList<TItem> list,
    Func<TItem, TKey> projection)
{
    // Do the binary search here.
    // TODO: Decide what to do if you can't find the right value... throw
    // an exception? Change the return type to return the *index* instead of the
    // value?
}

Upvotes: 3

dougajmcdonald
dougajmcdonald

Reputation: 20057

You can simply use .Find() to find an item in a list, without explicitely enumerating:

http://msdn.microsoft.com/en-us/library/x0b5b5bc.aspx

EDIT: Actually, looking in more detail it looks like this is a linear search and might not be what you want.

Upvotes: 0

Jonatan Hedborg
Jonatan Hedborg

Reputation: 4432

I assume it won't actually be 1:1 with array index and ID field (like in your example), or you could just use the []-method to find it.

Option 1 would be to add it to a Dictionary instead, and use ID field as key.

Option 2 is to write a makeshift binary search, starting at the middle of the array and checking if the current id is larger, smaller or correct. Then doing it again with the new sub-array until you find your ID.

Upvotes: 2

Colin Desmond
Colin Desmond

Reputation: 4854

Instead of a brute force, start-end, search, you could implement some kind of binary division and that should speed it up nicely. Or use the Dictionary type instead?

Upvotes: 0

Related Questions