Searching a sorted array
Once an array is sorted, you can perform a fast search for a particular item by using Arrays.binarySearch( ). However, it’s very important that you do not try to use binarySearch( ) on an unsorted array; the results will be unpredictable. The following example uses a RandIntGenerator to fill an array, and then uses the same generator to produce values to search for:
//: c11:ArraySearching.java
// Using Arrays.binarySearch().
import com.bruceeckel.util.*;
import java.util.*;
public class ArraySearching {
public static void main(String[] args) {
int[] a = new int[100];
Arrays2.RandIntGenerator gen =
new Arrays2.RandIntGenerator(1000);
Arrays2.fill(a, gen);
Arrays.sort(a);
System.out.println(
"Sorted array: " + Arrays2.toString(a));
while(true) {
int r = gen.next();
int location = Arrays.binarySearch(a, r);
if(location >= 0) {
System.out.println("Location of " + r +
" is " + location + ", a[" +
location + "] = " + a[location]);
break; // Out of while loop
}
}
}
} ///:~
In the while loop, random values are generated as search items until one of them is found.
Arrays.binarySearch( ) produces a value greater than or equal to zero if the search item is found. Otherwise, it produces a negative value representing the place that the element should be inserted if you are maintaining the sorted array by hand. The value produced is
-(insertion point) - 1
The insertion point is the index of the first element greater than the key, or a.size( ), if all elements in the array are less than the specified key.
If the array contains duplicate elements, there is no guarantee which one will be found. The algorithm is thus not really designed to support duplicate elements, but rather to tolerate them. If you need a sorted list of nonduplicated elements, use a TreeSet (to maintain sorted order) or LinkedHashSet (to maintain insertion order), which will be introduced later in this chapter. These classes take care of all the details for you automatically. Only in cases of performance bottlenecks should you replace one of these classes with a hand-maintained array.
If you have sorted an object array using a Comparator (primitive arrays do not allow sorting with a Comparator), you must include that same Comparator when you perform a binarySearch( ) (using the overloaded version of the method that’s provided). For example, the AlphabeticSorting.java program can be modified to perform a search:
//: c11:AlphabeticSearch.java
// Searching with a Comparator.
import com.bruceeckel.simpletest.*;
import com.bruceeckel.util.*;
import java.util.*;
public class AlphabeticSearch {
private static Test monitor = new Test();
public static void main(String[] args) {
String[] sa = new String[30];
Arrays2.fill(sa, new Arrays2.RandStringGenerator(5));
AlphabeticComparator comp = new AlphabeticComparator();
Arrays.sort(sa, comp);
int index = Arrays.binarySearch(sa, sa[10], comp);
System.out.println("Index = " + index);
monitor.expect(new String[] {
"Index = 10"
});
}
} ///:~
The Comparator must be passed to the overloaded binarySearch( ) as the third argument. In this example, success is guaranteed because the search item is selected from the array itself.
