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 List
s. 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
LinkedList
whose 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.
Frequently Asked Questions (FAQs) about Java’s Binary Search API
What is the purpose of Java’s Binary Search API?
Java’s Binary Search API is a powerful tool used for searching elements in an array or list. It uses the binary search algorithm, which is a divide and conquer strategy. This algorithm works by dividing the array into two halves and then searching the required element in one of the halves. This process continues until the element is found or the subarray size becomes zero. The Binary Search API is efficient and fast, making it ideal for handling large data sets.
How does the Binary Search API differ from other search methods in Java?
The Binary Search API differs from other search methods in Java primarily in terms of efficiency. While linear search methods scan each element of an array one by one, the Binary Search API divides the array into halves, significantly reducing the number of comparisons needed to find an element. However, it’s important to note that the Binary Search API requires the array to be sorted before it can be used.
Can I use the Binary Search API with unsorted arrays?
No, the Binary Search API cannot be used with unsorted arrays. The binary search algorithm works on the principle of dividing the array into two halves, which requires the array to be sorted. If the array is not sorted, the results of the binary search will be unpredictable.
How can I sort an array before using the Binary Search API?
Java provides several methods to sort an array. The simplest way is to use the Arrays.sort() method. This method sorts the specified array into ascending numerical order.
What happens if the element is not found in the array using Binary Search API?
If the element is not found in the array, the Binary Search API will return a negative value. This value is the “insertion point” which is the point at which the key would be inserted into the array.
Can I use the Binary Search API with arrays of objects?
Yes, you can use the Binary Search API with arrays of objects. However, the objects must implement the Comparable interface, and the array must be sorted according to the natural ordering of its elements.
What is the time complexity of the Binary Search API?
The time complexity of the Binary Search API is O(log n), where n is the number of elements in the array. This makes it a very efficient search method for large data sets.
Can I use the Binary Search API with lists?
Yes, you can use the Binary Search API with lists. The Collections class provides a binarySearch() method that works with lists. However, similar to arrays, the list must be sorted before you can use the binary search.
How does the Binary Search API handle duplicate elements in the array?
If there are duplicate elements in the array, the Binary Search API does not guarantee which one will be found. It will return the index of any of the duplicate elements.
Can I use the Binary Search API with arrays of primitive types?
Yes, you can use the Binary Search API with arrays of primitive types. The Arrays class provides overloaded binarySearch() methods for different primitive types like int, long, double, etc.
Jackie is a full-stack developer with several years of experience in Java EE web application development. He is currently working in the logistics industry and focused on delivering customer projects. His main interests are scalable enterprise systems, Java performance, data structures and algorithms.