Finding Array Elements Using Binary Searches

If the items in the array are sorted, you can search the array using a binary search. A binary search is optimized to eliminate parts of the array where the item can't possibly be. It does this roughly by looking at the middle of the array, seeing if the item is greater than or less than the search value, and discarding the half that does not contain the value.It then searches the middle of the portion that may contain the item and repeats the procedure until it finds the item. For binary searches to work you must sort the array but also, the class in the array must implement the IComparable interface illustrated in the section titled "Sorting." Most of the native classes already implement this interface.

To perform a binary search:

1. Type System.Array.BinarySearch .

2. Type an open parenthesis ( .

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

4. Type a comma , .

5. Type the value you wish to search for, or a variable that points to the object for which you wish to search, for example: "Jose" .

6. Type a close parenthesis ) .

7. Type a semicolon ; ( Figure 9.43 ).

   Figure 9.43 When BinarySearch is successful it returns a value similar to IndexOf (linear search), except that binary searches are faster than linear searches.

    void Task() {    string[] names = new string[]    {"Buffy","Kirk","Data","Wakka"};  Array.Sort(names);   int index = Array.BinarySearch(names,"Data");  if (index >= 0)    {       //found item, index = 2    } } 

Tip

• If the binary search fails to find the item, the function returns a negative value equivalent to the index that comes after the place where the item would have been, minus one. (You may be thinking, "Huh? Can you say that again?" I will.) Suppose that you have an array of letters A, B, D, E and you're searching for C. C isn't in the array, so BinarySearch would return -3. That's the index of the letter after the item we were searching for, which is D. D's index is 2 (because the array is zero based). Because it is a failure we turn that into a negative number, which is -2. We then use what is called the twos complement of the number, which in lay terms means we subtract 1 from the value, which gives us -3. Why do we subtract 1? Because zero is a valid index, so if the array contained B, C, D, E and we were looking for A, the next item after A is B. B has an index of zero, but we wouldn't return zero as the result because then we would think the index of A was zero, so the function always subtracts 1. There is an easy way to find the index from a failure return code using the ~ operator ( Figure 9.44 ).

  Figure 9.44 Papa Smurf isn't part of the array of names, so the function returns a negative number. In this case the number would be -4. Using the ~ operator we can convert that number to the actual index the where the item would have been if it had been part of the list.

   void Task() {    string[] names = new string[]    {"Buffy","Kirk","Data","Wakka"};    Array.Sort(names);    int index = Array.BinarySearch(names,"Papa Smurf");    if (index >= 0)    {       //item not found    }    else    {       System.Console.WriteLine(       "item should've been at " +  ~index  );  //returns 3  } }