Searching in Collections – Collections: Part II
By Jaime Williams / January 23, 2022 / No Comments / Composing Stream Pipelines, Oracle Certification Exam, The NavigableSet Interface
Searching in Collections
The Collections class provides two static methods for finding elements in sorted lists.
<E> int binarySearch(List<? extends Comparable<? super E>> list, E key)
<E> int binarySearch(List<? extends E> list, E key,
Comparator<? super E> cmp))
These methods use binary search to find the index of the key element in the specified sorted list. The first method requires that the list is sorted according to natural ordering, whereas the second method requires that it is sorted according to the total ordering dictated by the comparator. The elements in the list and the key must also be mutually comparable.
Successful searches return the index of the key in the list. A non-negative value indicates a successful search. Unsuccessful searches return a negative value given by the formula –(insertion point + 1), where insertion point is the index where the key would have been, had it been in the list. In the code below, the return value -3 indicates that the key would have been at index 2, had it been in the list.
Collections.sort(strList);
// Sorted in natural order: [Bigfoot, big, bigger, biggest]
// Search in natural order:
out.println(Collections.binarySearch(strList, “bigger”)); // Successful: 2
out.println(Collections.binarySearch(strList, “bigfeet”)); // Unsuccessful: -3
out.println(Collections.binarySearch(strList, “bigmouth”)); // Unsuccessful: -5
Proper use of the search methods requires that the list is sorted, and the search is performed according to the same sort order. Otherwise, the search results are unpredictable. The example below shows the results of the search when the list str-List above was sorted in reverse natural ordering, but was searched assuming natural ordering. Most importantly, the return values reported for unsuccessful searches for the respective keys are incorrect in the list that was sorted in reverse natural ordering.
Collections.sort(strList, Collections.reverseOrder());
// Sorted in reverse natural order: [biggest, bigger, big, Bigfoot]
// Searching in natural order:
out.println(Collections.binarySearch(strList, “bigger”)); // 1
out.println(Collections.binarySearch(strList, “bigfeet”)); // -1 (INCORRECT)
out.println(Collections.binarySearch(strList, “bigmouth”)); // -5 (INCORRECT)
Searching the list in reverse natural ordering requires that an appropriate comparator is supplied during the search (as during the sorting), resulting in correct results:
Collections.sort(strList, Collections.reverseOrder());
// Sorted in reverse natural order: [biggest, bigger, big, Bigfoot]
// Searching in reverse natural order:
out.println(Collections.binarySearch(strList, “bigger”,
Collections.reverseOrder())); // 1
out.println(Collections.binarySearch(strList, “bigfeet”,
Collections.reverseOrder())); // -3
out.println(Collections.binarySearch(strList, “bigmouth”,
Collections.reverseOrder())); // -1
The following methods search for sublists:
int indexOfSubList(List<?> source, List<?> target)
int lastIndexOfSubList(List<?> source, List<?> target)
These two methods find the first or the last occurrence of the target list in the source list, respectively. They return the starting position of the target list in the source list. The methods are applicable to lists of any type.
The following methods find the maximum and minimum elements in a collection:
<E extends Object & Comparable<? super E>>
E max(Collection<? extends E> c)
<E> E max(Collection<? extends E> c, Comparator<? super E> cmp)
<E extends Object & Comparable<? super E>>
E min(Collection<? extends E> c)
<E> E min(Collection<? extends E> cl, Comparator<? super E> cmp)
The one-argument methods require that the elements have a natural order-ing—that is, are Comparable<E>. The other methods require that the elements have a total ordering enforced by the comparator. Calling any of the methods with an empty collection as a parameter results in a NoSuchElementException.
The time for the search is proportional to the size of the collection.
These methods are analogous to the methods first() and last() in the SortedSet<E> class (p. 810), and the methods firstKey() and lastKey() in the SortedMap<K, V> class (p. 845).