#138 – Searching a Sorted Array

If an array is already sorted and if the type that its elements belong to has implemented IComparable, you can use the BinarySearch method to quickly search for a particular element.

Using our earlier example, with a Person class that implements IComparable (sorts by LastName/FirstName), we can search for a particular Person in a sorted array:

            Person[] folks = new Person[4];
            folks[0] = new Person("Bronte", "Emily");
            folks[1] = new Person("Bronte", "Charlotte");
            folks[2] = new Person("Tennyson", "Alfred");
            folks[3] = new Person("Mailer", "Norman");

            // Sort
            Array.Sort(folks);    // C. Bronte, E. Bronte, Mailer, Tennyson

            // Now search - returns index of 2 (3rd element)
            int normIndex = Array.BinarySearch(folks, new Person("Mailer", "Norman"));
            Person norm = folks[normIndex];     // Get reference to Normal

If you have a property not used for sorting purposes (e.g. Person.Age), you can’t be guaranteed that the object returned as a match actually matches your specified object–for that property.  Only properties used for comparison are guaranteed to match in the object returned.

Advertisements

About Sean
Software developer in the Twin Cities area, passionate about software development and sailing.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: