Finding Array Elements Using Linear Searches

The System.Array class enables you to obtain the index number of an item. You can perform a search through the arrays using two mechanisms: linear searching or binary searching. Binary searching is faster than linear searching, but binary searching requires that the items are sorted first. If you want to sort classes you designed yourself, you'll need to implement an interface called ICompareable (for details see the "Sorting" section). Linear searches are slower than binary searches but items in the array don't need to be in any particular order.

To search through an array linearly:

1. Type int index = , where index is any variable name to store the result of the search.

2. Type System.Array.IndexOf to search for the first instance of the item in the array. Type System.Array.LastIndexOf to find the last instance of the item in the array.

3. Type an open parenthesis ( .

4. Type the name of the array that you wish to search, for example: names .

5. Type a comma , .

6. Type the value you wish to search for, for example: "Jose" . Alternatively if you are searching for an instance of an object, type the name of the variable that stores the instance of the object for which you wish to search.

7. Type a close parenthesis ) .

8. Type a semicolon ; ( Figure 9.36 ).

   Figure 9.36 The IndexOf function gives the zero-based index of the element. It goes through each item comparing it to the sought value until it finds a match.

    void Task() {    string[] names = new string[]    {"Fred","Martha","James","Sally"};    int index = Array.  IndexOf  (names,"James");    if (index != -1)    {       //we've found the name in the list       //the index is 2    } } 

Tips

• Both search functions let you specify an index from which to start the search, and also limit the search to a certain range within the array ( Figure 9.37 ).

  Figure 9.37 If we were to use the first version of IndexOf to look for Martha we would always get the first instance of Martha in the list (index 1). But if we use the overloaded version that lets us specify the starting index we can tell it to skip the first one and start at index 2. The function then returns 4.

   void Task() {    string[] names = new string[]    {"Fred",  "Martha"  ,"James","Sally",  "Martha"  };    int index = Array.IndexOf(names,  "Martha",2  );    if (index != -1)    {       //we've found the name in the list  //the index is 4  } } 

• If the item can't be located, the IndexOf and the LastIndexOf functions returns the array's lower bound -1. Since the lower-bound is 99 percent of the time zero, the function normally returns -1 if it fails to find the item.

• Suppose you have an array of Checking accounts, and each Checking account has an AccountNumber field that identifies the account. How would you search the array for a particular AccountNumber? The IndexOf and LastIndexOf work with any type of object, but those functions merely navigate through each item in the array and call a function in System.Object called Equals on each element passing the object you specified in your search. To make the search meaningful for custom classes, you need to override the Equals function in your class. The search functions work fine with the primitive types because Microsoft has already implemented this function. Without overriding Equals the search functions only find a match if you look for the exact same object. They wouldn't work if you create a new object and set the fields to a value you're trying to match and then search. Figure 9.38 gives you an example of how to override Equals in a class.

  Figure 9.38 For IndexOf to work with custom objects, your class needs to override Equals from System.Object. The rules also say that if you override Equals you have to override GetHashCode as well. A hash code is a number that represents the data. If two objects are equal they should return the same hash code.

   class Person {    public string Name;    public int Age;    public Person(string name, int age)    {       Name = name;       Age = age;    }  public override bool Equals(   object obj)  {       if (obj is Person)       {          Person temp = (Person)obj;          if (temp.Age == this.Age &&          temp.Name == this.Name)          {             return true;          }       }       return false;    }  public override int GetHashCode()  {       return Age.GetHashCode() +       Name.GetHashCode();    } } void Task() {    Person[] friends = new Person[]       { new Person("Bill",28),         new Person("Jim",31),         new Person("Jason",29) };    Person seeker = new Person("Jim",31);    int index = Array.IndexOf(friends,    seeker); }