ArrayList Search .net

Question

Hi, Following is the format of the data stored in my arraylist.

A-Amsterdam
B- Brussels
C-Canada

so and so forth. I wan to search my array list by passing just the first few characters till '-' So if i have something like AA-Test then i want to pass just 'AA' to check if it exists or not.

I know that i can use contains or binarysearch but it does not serve my purpose as they both compare objects.

Any suggestions?? thanks

Answer 1

You can solve this by creating your own IComparer and passing it into BinarySearch:

public class StartsWithComparer : IComparer
{
    public int Compare(Object x, Object y)
    {
        String left = x as String;
        String right = y as String;

        if (ReferenceEquals(left, right))
        {
            return 0;
        }

        if (ReferenceEquals(left, null))
        {
            return -1;
        }

        if (ReferenceEquals(right, null))
        {
            return 1;
        }

        return (x.StartsWith(y) || y.StartsWith(x)) ? 0 : x.CompareTo(y);
    }
}

Later...

myArrayList.Sort()
myArrayList.BinarySearch("AA", new StartsWithComparer());

Answer 2

You may want to take into account the size of the arraylist and the number of lookups you'll be doing:

If you've got a large number of elements in your dataset, (a large arraylist) or a large number of lookups, you'll want to use a search algorithm like binary search

If the data is sufficiently large though, you may consider storing your data in a hashtable indexed by the first few characters that you want to access it by ('AA' in your example).

Lastly, for a small arraylist size and a large number of lookups, you may find that using the same comparer function with a linear search actually performs better. This has been discussed further here: http://stackoverflow.com/questions/1275665/at-which-n-does-binary-search-become-faster-than-linear-search-on-a-modern-cpu