You
have a data type that will be stored
as elements in an array or an ArrayList
. You would
like to use the Array.BinarySearch
and
ArrayList.BinarySearch
methods to allow for custom
searching of your data types in the array.
Use the IComparable
and IComparer
interfaces. The
Square
class, from Recipe 3.5, implements these in a way so that the
Array
, ArrayList
, and
SortedList
objects can sort and search an array or
collection of Square
objects.
By implementing the IComparable
interface on your
class (or structure), you can take advantage of the search routines
of the Array
, ArrayList
, and
SortedList
classes. The algorithms for searching
are built into these classes; all you have to do is tell them how to
search through your classes via the code you implement in the
IComparable.CompareTo
method.
To implement the CompareTo
method, see Recipe 3.5.
The Array
and ArrayList
classes
provide a BinarySearch
method to perform a search
on the elements in that array. The elements are compared against an
object passed to the BinarySearch
method in the
object parameter.
The SortedList
class
does not have a BinarySearch
method; instead, it
has Contains
, ContainsKey
, and
ContainsValue
methods to perform a linear search
when searching for values. This linear search uses the
Equals
method of the elements in the
SortedList
collection to do its work (to overload
the Equals
method, see Recipe 3.9), the Compare
and
CompareTo
methods do not have any effect on the
operation of the linear search performed in the
SortedList
class, but they do have an effect on
binary searches.
To perform an accurate search using the
BinarySearch
methods of the
Array
and ArrayList
classes,
you must first sort the Array
or
ArrayList
using its Sort
method. In addition, if you pass an IComparer
interface to the BinarySearch
method, you must
also pass the same interface to the Sort
method.
Otherwise, the BinarySearch
method might not be
able to find the object you are looking for.
The following method shows how to use the Square
and CompareHeight
structures with the
Array
, ArrayList
, and
SortedList
classes:
public static void TestSort( ) { Square[] arrayOfSquares = new Square[4] {new Square(1,3), new Square(4,3), new Square(2,1), new Square(6,1)}; ArrayList arrayListOfSquares = new ArrayList( ); arrayListOfSquares.Add(new Square(1,3)); arrayListOfSquares.Add(new Square(4,3)); arrayListOfSquares.Add(new Square(2,1)); arrayListOfSquares.Add(new Square(6,1)); IComparer HeightCompare = new CompareHeight( ); // Test an ARRAY Console.WriteLine("ARRAY"); Console.WriteLine("Original array"); foreach (Square s in arrayOfSquares) { Console.WriteLine(s.ToString( )); } Console.WriteLine( ); Console.WriteLine("Sorted array using IComparer=HeightCompare"); Array.Sort(arrayOfSquares, HeightCompare); foreach (Square s in arrayOfSquares) { Console.WriteLine(s.ToString( )); } Console.WriteLine( ); Console.WriteLine("Search using IComparer=HeightCompare"); int found = Array.BinarySearch(arrayOfSquares, new Square(1,3), HeightCompare); Console.WriteLine("found (1,3): " + found); Console.WriteLine( ); Console.WriteLine("Sorted array using IComparable"); Array.Sort(arrayOfSquares); foreach (Square s in arrayOfSquares) { Console.WriteLine(s.ToString( )); } Console.WriteLine("Search using IComparable"); found = Array.BinarySearch(arrayOfSquares, new Square(6,1), null); // Use IComparable Console.WriteLine("found (6,1): " + found); // Test an ARRAYLIST Console.WriteLine( ); Console.WriteLine( ); Console.WriteLine("ARRAYLIST"); foreach (Square s in arrayListOfSquares) { Console.WriteLine(s.ToString( )); } Console.WriteLine( ); Console.WriteLine("Sorted ArrayList using IComparer=HeightCompare"); arrayListOfSquares.Sort(HeightCompare); foreach (Square s in arrayListOfSquares) { Console.WriteLine(s.ToString( )); } Console.WriteLine( ); Console.WriteLine("Search using IComparer=HeightCompare"); found = arrayListOfSquares.BinarySearch(new Square(1,3), HeightCompare); Console.WriteLine("found (1,3): " + found); Console.WriteLine( ); Console.WriteLine("Sorted ArrayList using IComparable"); arrayListOfSquares.Sort( ); foreach (Square s in arrayListOfSquares) { Console.WriteLine(s.ToString( )); } Console.WriteLine( ); Console.WriteLine("Search using IComparable"); found = arrayListOfSquares.BinarySearch(new Square(6,1), null); Console.WriteLine("found (6,1): " + found); // Test a SORTEDLIST SortedList SortedListOfSquares = new SortedList( ); SortedListOfSquares.Add(0, new Square(1,3)); SortedListOfSquares.Add(2, new Square(4,3)); SortedListOfSquares.Add(1, new Square(2,1)); SortedListOfSquares.Add(3, new Square(6,1)); Console.WriteLine( ); Console.WriteLine( ); Console.WriteLine("SORTEDLIST"); foreach (DictionaryEntry s in SortedListOfSquares) { Console.WriteLine(s.Key + " : " + ((Square)s.Value).ToString( )); } Console.WriteLine( ); bool foundBool = SortedListOfSquares.Contains(2); Console.WriteLine("SortedListOfSquares.Contains(2): " + foundBool); foundBool = SortedListOfSquares.ContainsKey(2); Console.WriteLine("SortedListOfSquares.ContainsKey(2): " + foundBool); // Does not use IComparer or IComparable // -- uses a linear search along with the Equals method, which has not been // overloaded; if the Square object were to be used as the key // rather than the value, a binary search would be performed when searching // for this Square object. Square value = new Square(6,1); foundBool = SortedListOfSquares.ContainsValue(value); Console.WriteLine ("SortedListOfSquares.ContainsValue(new Square(6,1)): " + foundBool); }
This code displays the following:
ARRAY Original array Height:1 Width:3 Height:4 Width:3 Height:2 Width:1 Height:6 Width:1 Sorted array using IComparer=HeightCompare Height:1 Width:3 Height:2 Width:1 Height:4 Width:3 Height:6 Width:1 Search using IComparer=HeightCompare found (1,3): 0 Sorted array using IComparable Height:2 Width:1 Height:1 Width:3 Height:6 Width:1 Height:4 Width:3 Search using IComparable found (6,1): 2 ARRAYLIST Height:1 Width:3 Height:4 Width:3 Height:2 Width:1 Height:6 Width:1 Sorted ArrayList using IComparer=HeightCompare Height:1 Width:3 Height:2 Width:1 Height:4 Width:3 Height:6 Width:1 Search using IComparer=HeightCompare found (1,3): 0 Sorted ArrayList using IComparable Height:2 Width:1 Height:1 Width:3 Height:6 Width:1 Height:4 Width:3 Search using IComparable found (6,1): 2 SORTEDLIST 0 : Height:1 Width:3 1 : Height:2 Width:1 2 : Height:4 Width:3 3 : Height:6 Width:1 SortedListOfSquares.Contains(2): True SortedListOfSquares.ContainsKey(2): True SortedListOfSquares.ContainsValue(new Square(6,1)): False
See Recipe 3.5 and Recipe 3.9; see the “IComparable Interface” and “IComparer Interface” topics in the MSDN documentation .