Fastest way to find an item in a list?

Question

I have an unsorted list of strings. I can place these items in an array, List, SortedList, whatever.

I need to find the fastest way of looking up a string in this list. Am I better off dumping the list into an array, sorting it, then implementing binary search? Or does the framework provide a way to do this?

Thanks

P.S. Using VS2008 against .NET 2.0

Answer 1

If your goal is just to make it very fast to find the strings in a collection, put them into a HashSet.

HashSet.Contains is an O(1) method, and strings have a good hash algorithm by default, so it will be difficult to make a faster routine than this.

---

Edit:

Since you're using .NET 2, I would just do Dictionary<string,string> and use the same string for key and value. Dictinoary<TKey,TValue>.Contains is also O(1), and will be much faster than any list-based searching you attempt.

Answer 2

If you will only have to find one object, one time, just start at the beginning and look at each one until you find it. If you will have to repeat this Find operation multiple times against the same list, to find different items, then sort it keep the sorted list and do a binary search...

Answer 3

I'm not sure whether this will be of any use to you, but this would be a fairly simple way of doing it, not sure on the exact "speed" of it though.

List<string> collection = new List<string>();

collection.Sort();

foreach(string value in collection)
{
   if(value == "stringToLookFor")
   {
       return value;
   }
{