C# Fast way to find value in a jagged Array

Question

I have a jagged Array String[][]. Now I need to find the array with a particular value in String[n][0] what i have a the moment is a simple

foreach foo in bar{
 if(foo[0]==needle){
  return foo;
 }
}

As you may see this is very slow for obvious reasons. I'm new to C# and just saw the indexOf, but how can i use indexOf in a jagged array?

Another way i tought of is Sorting the Array by String[n][0], going to the record in the middle, check if my value is larger or bigger, jump in the half of the upper/lower area and so on, maybe 3 or 4 times so i can find the record faster.

So whats the fastest way of getting the Array in a jagged Array where I only know [][0]?

Answer 1

I would use a Dictionary<int, int[]> where the key is the first item of the array. Dictionaries have constant time access, and are very fast for random access if the entire data fits in memory.

Answer 2

Well, you are searching for a value than can be on array[i][0] for every i from 0 to n, right? Then, it has nothing to do with jagged arrays, but with finding a value in a collection (which in your case is the collection of {array[i][0], for each 0 <= i < n )

If you're going to search only once, then the best thing that can be done is your own solution, that runs on linear time: O(n)

If your're going to search many times (without changind array[i][0] for any i) then you can sort the array by String[n][0] and do a "binary search", which is exactly the algorithm you described. Sorting will take O(n lgn) of time. But each search will be very fast O(lg n).

Answer 3

Perhaps rather than a jagged array, you'd be better suited with a Dictionary, where the key is the first item of each of your arrays. Since dictionaries are hash tables, look ups should be fast.

// Some test data.    
var dictionary = new Dictionary<string, string[]>
{
    { "foo1", new string[] { "foo1", "bar1" }},
    { "foo2", new string[] { "foo2", "bleh" }},
    { "foo3", new string[] { "foo3", "bar3", "hello", "world" }},
    { "foo4", new string[] { "foo4",  }},
    { "foo5", new string[] { "foo5", "bar5", "test" }},
};

string[] item = dictionary["foo3"]; // Fast look up.