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.

---

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

---

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?
}

---

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.

---

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?

---

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.

---

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.

---

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)

---

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