Searching for the beginning of a string in an array in C#

Question

I have a List containing a lot of paths. I have a specific path I want to check against this list to see if there are any paths there that uses this path, ie:

f.StartsWith(r.FILENAME) && f != r.FILENAME

What would be the fastest way of doing this?

edit: Complete function from answer below:

static bool ContainsFragment(string[] paths, string fragment)
{
    // paths **must** be pre-sorted via Array.Sort(paths);
    if (paths.Length == 0) return false;
    int index = Array.BinarySearch(paths, fragment);
    if (index >= 0 && index+1 < paths.Length)
    { //we found it 
        if (paths[index + 1].StartsWith(fragment) &&
            paths[index + 1].EndsWith(".manifest"))
        {
            return true;
        }
    }
    return false;
}

Answer 1

The fastest way is probably with binary search:

static bool ContainsFragment(string[] paths, string fragment)
{
    // paths **must** be pre-sorted via Array.Sort(paths);
    if (paths.Length == 0) return false;
    int index = Array.BinarySearch(paths, fragment);
    // we want the index of the *next highest* path
    if (index < 0) { // no match
        index = ~index; 
    } else { // exact match
        index++; // for strict substring (non-equal)
    }
    return index < paths.Length && paths[index].StartsWith(fragment);
}

But the cost of sorting the array will outweigh any benefit if you are only doing it a few times; in which case, just scan the array - either with LINQ etc, or just:

bool found = false;
for(int i = 0 ; i < paths.Length ; i++) {
    if(paths[i].StartsWith(fragment) &&
          paths[i].Length != fragment.Length)
    {
        found = true;
        break;
    }
}

Answer 2

var matches = list.Where(f => f.StartsWith(r.FILENAME) && f != r.FILENAME);

Or if you only care about existence:

bool any = list.Any(f => f.StartsWith(r.FILENAME) && f != r.FILENAME);

This is assuming you're using .NET 3.5, admittedly - otherwise there are similar methods in List<T> and you can use an anonymous method.

Answer 3

What I find interesting about this relatively simple question is the number of "valid" answers, depending on how you define "fastest."

• If fastest means "least costly," then Marc's binary search method sounds like your answer.
• If fastest means "quickest to implement," then Jon's list.Any method call is appropriate.
• If fastest means "brute force," then you may want to look at parallelizing the search. It will be more costly in terms of processing required, but may execute more quickly depending on your server resources. PLINQ gives you a good starting point for this.