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


  • Read Part 1

  • 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


    Copyright 2017 QuinStreet Inc. All Rights Reserved.
    Legal Notices, Licensing, Permissions, Privacy Policy.
    Advertise | Newsletters | E-mail Offers