IComparer for string that checks if x starts with y

Question

I've got an array of strings and I need to get all strings, that start with some 'prefix'. I wanna use Array.BinarySearch(). Is it possible? And how should I write a comparer if so?

Answer 1

No, you cannot use BinarySearch in this case. You could use Enumerable.Where instead:

Dim query = From str In array Where str.StartsWith("prefix")

or with (ugly in VB.NET) method synatx:

query = array.Where(Function(str) str.StartsWith("prefix"))

Edit: whoops, C#

var query = array.Where(s => s.StartsWith("prefix"));

Use ToArray if you want to create a new filtered array.

Answer 2

It's easy to create your own StartsWithComparer:

class StartsWithComparer : IComparer<string>
{
    public int Compare(string a, string b) {
        if(a.StartsWith(b)) {
            return 0;
        }
        return a.CompareTo(b);
    }
}

As others pointed out, this will only return one index. You can have a couple of helpers to return all items:

IEnumerable<string> GetBefore(IList<string> sorted, int foundIndex, string prefix) {
    for(var i = foundIndex - 1; i >= 0; i--) {
        if(sorted[i].StartsWith(prefix)) {
            yield return sorted[i];
        }
    }
}

IEnumerable<string> GetCurrentAndAfter(IList<string> sorted, int foundIndex, string prefix) {
    for(var i = foundIndex; i < sorted.Count; i++) {
        if(sorted[i].StartsWith(prefix)) {
            yield return sorted[i];
        }
    }
}

Then to use it:

var index = sorted.BinarySearch("asdf", new StartsWithComparer());
var previous = GetBefore(sorted, index, "asdf");
var currentAndAfter = GetCurrentAndAfter(sorted, index, "asdf");

You can wrap the whole thing in your own class, with a single method that returns all items that start with your prefix.