To read the article online, visit http://www.4GuysFromRolla.com/articles/110602-1.2.aspx

# Efficiently Searching a Sorted Array, Part 2

By Scott Mitchell

• In Part 1 we discussed the basics of the binary search algorithm. Additionally, we looked at how to use the `Array.BinarySearch` method to determine if an array element that implements the `IComparable` interface exists in an array or not. In this part we'll examine how to use the `Array.BinarySearch` method on arrays whose elements do not implement the `IComparable` interface.

## Using `Array.BinarySearch` for Array Elements that are not Intuitively Comparable

Recall that the binary search algorithm requires that not only the array be in sorted order, but that its elements be comparable. That is, when running the binary search algorithm to see if some value exists in the array, we must be able to compare the value we're searching for with the current array element we're interested in to determine if the value we're searching for is equal, "less than", or "greater than" the array element value. If your array stores simple data types, like strings or integers, these can easily be compared. However, what if you are storing, say, a custom class in each array element? How the `Array.BinarySearch` method compare the value you're searching for with the array elements?

The short answer is it can't, not if you don't provide it some help. Specifically, to use the `Array.BinarySearch` method on an array whose elements do not implement the `IComparable` interface you must provide a comparing function. That is, you must pass into the `Array.BinarySearch` method a function that, when given two elements, can determine how they relate to one another - if the first one is greater than, less than, or equal to the second.

Imagine that you have created a custom class, `Student`, that has two public properties, `Name` and `Age`, which specify the name and age of the student. To create such a class using C#, you might use the following code:

 ```using System; public class Student { private string m_name; private int m_age; public Student() { m_name = ""; m_age = -1; } public Student(string name, int age) { m_name = name; m_age = age; } public string Name { get { return m_name; } set { m_name = value; } } public int Age { get { return m_age; } set { if (value > 0) m_age = value; } } } ```

To use this class in an ASP.NET Web page, you'd need to simply compile the class into a DLL and copy the DLL to the appropriate `/bin` directory. (For more information on creating custom classes and their benefits, be sure to read: Displaying Custom Classes in a DataGrid.) Now, image that you create an array of `Student` objects and that the array is sorted by the student's name. It would be nice to be able to use the `Array.BinarySearch` method to quickly determine if a given student exists in the array. Unfortunately there's no way for the `Array.BinarySearch` method to know how to compare the value of one `Student` object with another.

Fortunately, we can create a class that implements the `IComparer` interface that instructs the `Array.BinarySearch` method how to compare the value of two `Student` instances. Let's choose to compare the `Name` properties of the two `Student` instances to determine if they're equal. (We could, optionally, compare the `Name` and `Age` properties, but for this example let's just examine comparing the `Name` property.)

A class that implements the `IComparer` interface must implement one method: `Compare`, which takes as input two objects, `x` and `y`, and performs a comparison. The function returns 0 if the two objects are equal, a number less than zero if `x` is less than `y`, and a number greater than zero if `x` is greater than `y`. When calling this method, the `Array.BinarySearch` method will be passing in the array element being inspected and the value being searched for.

The `CompareCustomDataType` class provided below performs a comparison between two `Student` instances. It implements the `IComparer` interface and provides a `Compare` function that compares two `Student` instances by their `Name` property:

 ```using System; using System.Collections; public class CompareCustomDataType : IComparer { public int Compare(Object x, Object y) { if (x == null) return -1; if (y == null) return 1; Student xStudent = (Student) x; Student yStudent = (Student) y; return String.Compare(xStudent.Name, yStudent.Name); } } ```

The `CompareCustomDataType` class utilizes the `String` class's `Compare` method to compare the value of the two `Student` class instances. Also note that before comparing the two students they must be cast from type object to type `Student`. As with the `Student` class, the `CompareCustomDataType` class needs to be compiled and its resulting DLL placed in the Web application's `/bin` directory.

Once the `Student` and `CompareCustomDataType` classes have been compiled and their DLLs copied into the `/bin` directory, they can be used in an ASP.NET Web page. The following code demonstrates how an array of `Students` can be created and sorted (using `Array.Sort`, passing in a `CompareCustomDataType` class instance), and then having the `Array.BinarySearch` method be used to determine if a particular student exists in the array.

 ```'Create an array of 5 students Dim myArray(4) as Student myArray(0) = New Student("Scott", 24) myArray(1) = New Student("Jisun", 23) myArray(2) = New Student("Spacey", 21) myArray(3) = New Student("John", 23) myArray(4) = New Student("Josh", 20) 'Sort the array Array.Sort(myArray, New CompareCustomDataType) 'Determine if a particular student exists in the array Dim studentTemp as New Student() studentTemp.Name = "Jisun" location = Array.BinarySearch(myArray, studentTemp, New CompareCustomDataType) If location < 0 then 'Student Jisun does not exist in the array Else 'Student Jisun exists in the array at position location End If ```
[View a Live Demo!]

## Conclusion

In this article we examined how to use the `Array.BinarySearch` method to quickly determine if a particular element exists within a sorted array. (If you are not using ASP.NET you may be interested in this classic ASP version provided by Brandon Hunt.) Keep in mind that the array to which you apply the binary search must be sorted! Furthermore, the elements of the array must be comparable, meaning they either must implement the `IComparable` interface, or a class that implements the `IComparer` interface must be provided.

Happy Programming!

• By Scott Mitchell

•  Article Information Article Title: ASP.NET.Efficiently Searching a Sorted Array, Part 2 Article Author: Scott Mitchell Published Date: November 6, 2002 Article URL: http://www.4GuysFromRolla.com/articles/110602-1.2.aspx