Searching in Arrays – Collections: Part II
By Jaime Williams / October 23, 2022 / No Comments / Composing Stream Pipelines, Executing Stream Pipelines, Introduction to Streams, Oracle Certification Exam, Replacing Elements in Collections, The NavigableSet Interface
Searching in Arrays
A common operation on an array is to search the array for a given element, called the key. The Arrays class provides enough overloaded versions of the binarySearch() method to search in practically any type of array that is sorted. The discussion on searching in lists (p. 861) is also applicable to searching in arrays.
int binarySearch(
type
[] array,
type
key)
int binarySearch(
type
[] array, int fromIndex, int toIndex,
type
key)
The permitted type for elements includes byte, char, double, float, int, long, short, and Object.
These methods search for key in the array where the elements are sorted according to the natural ordering of the elements.
In the case where an array of objects is passed as an argument, the objects must be sorted in natural ordering, as defined by the Comparable<E> interface.
These methods return the index to the key in the sorted array, if the key exists. If not, a negative index is returned, corresponding to –(insertion point + 1), where insertion point is the index of the element where the key would have been found, if it had been in the array. In case there are duplicate elements equal to the key, there is no guarantee which duplicate’s index will be returned. The elements and the key must be mutually comparable.
The bounds, if specified in the methods, define a half-open interval. The search is then confined to this interval.
<E> int binarySearch(E[] array, E key, Comparator<? super E> c)
<E> int binarySearch(E[] array, int fromIndex, int toIndex, E key,
Comparator<? super E> c)
These two generic methods require that the array is sorted according to the total ordering dictated by the comparator. In particular, its elements are mutually comparable according to this comparator. The comparator must be equivalent to the one that was used for sorting the array; otherwise, the results are unpredictable.
An appropriate import statement should be included in the source code to access the java.util.Arrays class by its simple name. The experiment from p. 861 with a list of strings is repeated here with an array of strings, giving identical results. In the code below, the return value -3 indicates that the key would have been found at index 2 had it been in the list.
Arrays.sort(strArray);
// Sorted according to natural order: [Bigfoot, big, bigger, biggest]
// Search in natural order:
out.println(Arrays.binarySearch(strArray, “bigger”)); // Successful: 2
out.println(Arrays.binarySearch(strArray, “bigfeet”)); // Unsuccessful: -3
out.println(Arrays.binarySearch(strArray, “bigmouth”)); // Unsuccessful: -5
Results are unpredictable if the array is not sorted, or the ordering used in the search is not the same as the sort order. Searching in the strArray using reverse natural ordering when the array is sorted in natural ordering gives the wrong result:
out.println(Arrays.binarySearch(strArray, “bigger”,
Collections.reverseOrder())); // -1 (INCORRECT)
A ClassCastException is thrown if the key and the elements are not mutually comparable:
out.println(Arrays.binarySearch(strArray, 4)); // Key: 4 => ClassCastException
However, this incompatibility is caught at compile time in the case of arrays with primitive values:
// Sorted int array (natural order): [1, 3, 5, 7]
out.println(Arrays.binarySearch(intArray, 4.5));// Key: 4.5 => Compile-time error!
The method binarySearch() derives its name from the divide-and-conquer algorithm that it uses to perform the search. It repeatedly divides the remaining elements to be searched into two halves and selects the half containing the key in which to continue the search, until either the key is found or there are no more elements left to search.