Searching Arrays and Collections

The Collections class and the Arrays class both provide methods that allow you to search for a specific element. When searching through collections or arrays, the following rules apply:

• Searches are performed using the binarySearch() method.
• Successful searches return the int index of the element being searched.
• Unsuccessful searches return an int index that represents the insertion point. The insertion point is the place in the collection/array where the clement would be inserted to keep the collection/array properly sorted. Because positive return values and 0 indicate successful searches, the binarysearch() method uses negative numbers to indicate insertion points. Since 0 is a valid result for a successful search, the first available insertion point is -1. Therefore, the actual insertion point is represented as (-(insertion point) -1). For instance, if the insertion point of a search is at element 2, the actual insertion point returned will be -3.
• The collection/array being searched must be sorted before you can search it.
• If you attempt to search an array or collection that has not already been sorted, the results of the search will not be predictable.
• If the collection/array you want to search was sorted in natural order, it must be searched in natural order. (This is accomplished by NOT sending a Comparator as an argument to the binarysearch() method.)
• If the collection/array you want to search was sorted using a Comparator, it must be searched using the same Comparator, which is passed as the second argument to the binarysearch() method. Remember that Comparators cannot be used when searching arrays of primitives.

Let's take a look at a code sample that exercises the binarysearch() method:

import java.util.*;
class SearchObjArray {
    public static void main(String [] args) {
        String [] sa = {"one", "two", "three", "four"};
        Arrays.sort(sa);                                // #1
        for(String s : sa)
            System.out.print(s + " "};
        System.out.println("\none = "
                + Arrays.binarysearch(sa,"one"));            // #2
        System.out.println("now reverse sort");
        ReSortComparator rs = new ReSortComparator();    // #3
        Arrays.sort(sa,rs);
        for(String s : sa)
            System.out.print(s + " ");
        System.out.println("\none = "
                + Arrays.binarysearch(sa,"one"));            // #4
        System.out.println("one = "
                + Arrays.binarysearch(sa,"one",rs));        // #5
    }
    static class ReSortComparator
            implements Comparator {                // #6
        public int compare(String a, String b) {
            return b.compareTo(a);                        // #7
        }
    }
}

which produces something like this:

four one three two
one = 1
now reverse sort
two three one four
one = -1
one = 2

Here's what happened:

Line 1: Sort the sa array, alphabetically (the natural order).
Line 2: Search for the location of element "one", which is 1.
Line 3: Make a Comparator instance. On the next line we re-sort the array using the Comparator.
Line 4: Attempt to search the array. We didn't pass the binarySearch () method the Comparator we used to sort the array, so we got an incorrect (undefined) answer.
Line 5: Search again, passing the Comparator to binarysearch(). This time we get the correct answer, 2
Line 6: We define the Comparator; it's okay for this to be an inner class.
Line 7: By switching the use of the arguments in the invocation of compareTo(), we get an inverted sort.

Given:

1. import java.util.*;
2. public class Quest{
3.     public static void main(String[] args){
4.         String[] colors = 
5.                 {"blue","red","green","yellow","orange"};
6.         Arrays.sort(colors);
7.         int s2 = Arrays.binarySearch(colors, "orange");
8.         int s3 = Arrays.binarySearch(colors, "violet");
9.         System.out.print(s2 + "" + s3);
10.     }
11. }

What is the result?

A. 2-1
B. 2-4
C. 2-5
D. 3-1
E. 3-4
F. 3-5
G. Compilation fails.
H. An exception is thrown at runtime.

C