###
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.