Java’s Binary Search API in Five Minutes
Table of Contents
Binary search is a very efficient search algorithm that finds an item in a sorted array by repeatedly cutting down the search range by half. As a result, run time is logarithmic, or O(log n). This post teaches you how to use Java’s Arrays.binarySearch and Collections.binarySearch for searching sorted arrays or array lists considerably faster than you could using the linear search methods like a for loop or List.contains.
At a minimum, only working knowledge of arrays and lists is required. Knowing about Comparable and Comparator comes in handy.
Searching with Binary Search
Java’s binary search function can be found in java.util.Arrays and java.util.Collections APIs. The Arrays API provides the implementation for arrays.
Searching an Array
In its simplest form, the static method Arrays.binarySearch takes an array of any primitive type (as well as Object or reference type) and a search key, for examples:
static int binarySearch(int[] a, int key)static int binarySearch(char[] a, char key)static int binarySearch(Object[] a, Object key)
The methods return an int representing the index of the found search key within the array, or otherwise a negative value (whose significance I’ll explain in a moment) if it is not found.
Here’s a code example:
int[] numbers = {2, 3, 5, 7};
System.out.println("index of 5 is "
+ Arrays.binarySearch(numbers, 5));
// index of 5 is 2
Before you use the binary search function, make sure the array is already sorted into ascending order (for example, with the Arrays.sort method), otherwise the results will be unexpected.
Searching a Range
If you are supposed to only search a range of the specified array for the search key, you can use this overload:
Note that the toIndex is exclusive to be searched. With the preceding example, if you want to only search the array from index 0 up to 2 (inclusive), you write:
Arrays.binarySearch(numbers, 0, 3, 5);
Searching with a Comparator
If you are using the binary search method for an Object array, the elements of the array must either implement the Comparable interface or a Comparator must be specified:
The Comparator object is used by the binary search to compare the ordering of two objects so that it can determine whether an object comes before or after the other within the array during the search. In other words, the APIs do not limit an Object array to ascending/ natural order.
The array can be in any sort order as long as you can provide a Comparator which imposes an ordering consistent to the array’s sort order. In the simplest case, you have used the same comparator to sort the array with Arrays.sort(T[] a, Comparator<? super T> c).
Here’s an example to search an Integer array in descending order:
Integer[] numbers = {2, 3, 5, 7};
// sort numbers into reverse natural order, i.e. {7, 5, 3, 2}
Arrays.sort(numbers, Collections.reverseOrder());
// search using a reverse natural order comparator
System.out.println("index of 5 is " +
Arrays.binarySearch(numbers, 5, Collections.reverseOrder()));
// index of 5 is 1
Searching a List
The Java’s Collections class, on the other hand, provides the binary search function for operating on Lists. The two versions of the overloaded Collections.binarySearch method are:
static int binarySearch(List<? extends Comparable<? super T>> list, T key)static int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
The usage of these methods are similar to Arrays.binarySearch except the methods take a List of objects rather than an array.
Here’s an example:
List<Integer> numbers = Arrays.asList(2, 3, 5, 7);
System.out.println("index of 5 is "
+ Collections.binarySearch(numbers, 5));
// index of 5 is 2
Caveat: It is unwise to use binary search on a
LinkedListwhose implementation only allows sequential access to its elements, causing the binary search algorithm to perform very poorly.
Binary Search for Insertion
The APIs of both Arrays.binarySearch and Collections.binarySearch have a special behavior when they couldn’t find the given search key in the specified array or list: In that case the binary search method in both classes returns a negative value that is equivalent to - <insertion point> - 1, where insertion point is defined as the index at which the search key would be inserted into the array or list.
Here’s an example:
List<Integer> numbers = new ArrayList<>(
Arrays.asList( 2, 3, 5, 7, 11, 13, 17, 19, 23, 29));
System.out.println("index of 5 is "
+ Collections.binarySearch(numbers, 5));
System.out.println("index of 23 is "
+ Collections.binarySearch(numbers, 23));
System.out.println("index of 9 is "
+ Collections.binarySearch(numbers, 9));
System.out.println("index of 31 is "
+ Collections.binarySearch(numbers, 31));
The output:
index of 5 is 2
index of 23 is 8
index of 9 is -5
index of 31 is -11
In this example, integers 9 and 31 do not exist in the list. With the returned negative value, 9 would have been inserted at index 4, pushing the original entries at indices 4 and after one slot backward. The value of 31 would have been inserted at index 10, which is at the end of the list. If we were to insert 9 into the list, we could write code like this:
int pos = Collections.binarySearch(numbers, 9);
if (pos < 0) {
numbers.add(Math.abs(pos)-1, 9);
}
This feature of binary search is particularly useful for implementing the insertion function for some sort of priority queue for example, that uses an array to store its entries in ascending order. The insertion point can be used to insert the new entry into the queue accordingly.
Wrapping Up
Java’s standard binary search methods on java.util.Arrays and java.util.Collections allow you to find an item or locate the insertion point for a new item within an array or list. Binary search works only on sorted arrays or lists. It has logarithmic run time, making it very efficient for big data structures: Given a sorted array of size 100,000, the maximum required steps for binary search to find an item are log(100,000) / log(2) ≈ 17. On small data structures, the added overhead can make binary search slower than a linear scan.
