Skip to content
Tutorials Center
My learning

Topics

Java Reference ยท Collections

Java Arrays.binarySearch()

Reference for Arrays.binarySearch(): search a sorted array in O(log n), read the negative insertion-point result, and use a Comparator.

Arrays.binarySearch() looks for a value in a sorted array by repeatedly halving the range. It runs in O(log n) instead of the O(n) of a linear scan. The result is the index of the match if one is found. If not, it returns a negative number that tells you where the value would have to be inserted to keep the array sorted.

The array must already be sorted in ascending order (according to the same ordering the search uses). On an unsorted array the result is undefined: you may get a wrong index or a false negative, and no exception warns you.

Java
int[] sorted = {2, 5, 8, 12, 20};
int i = Arrays.binarySearch(sorted, 12);   // 3
int j = Arrays.binarySearch(sorted, 6);    // -3 (insertion point 2)

Try it

Java Found and not found

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Java Strings, comparators and duplicates

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Syntax

Java
static int binarySearch(int[] a, int key)
static int binarySearch(int[] a, int fromIndex, int toIndex, int key)
static int binarySearch(Object[] a, Object key)
static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
static <T> int binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c)

Overloads exist for byte, short, char, int, long, float, double and Object.

Name Description
a The sorted array to search.
key The value to look for.
fromIndex, toIndex Optional range: start inclusive, end exclusive.
c Optional comparator; null means natural ordering.

Returns: the index of the key if found; otherwise -(insertionPoint) - 1, where the insertion point is the index of the first element greater than the key (or the array length). The result is >= 0 exactly when the key was found.

Throws: IllegalArgumentException if fromIndex > toIndex, ArrayIndexOutOfBoundsException if the range is outside the array, ClassCastException if elements cannot be compared with the key, and NullPointerException when the array is null.

Usage notes

  • Sort first. Run Arrays.sort() once, then search many times. Sorting for a single search is slower than a linear scan.
  • Test with < 0, not == -1. Only a missing key at the very start gives -1; other misses give -2, -3 and so on.
  • Insertion point: -result - 1 (or ~result) turns a miss into the index where you would insert to keep the array sorted.
  • Duplicates: the result is not guaranteed to be the first or last equal element. If you need a boundary, write your own lower-bound loop.
  • Same ordering for sort and search. Sorting with a comparator and searching by natural order gives garbage results.
  • Floating point: -0.0 is less than 0.0 and NaN is greater than everything, matching Double.compare().
  • List version: Collections.binarySearch(list, key) is O(log n) on an ArrayList but O(n) on a LinkedList, because moving to the middle takes linear time.
  • Overflow-safe: the JDK computes the midpoint with an unsigned shift, so very large arrays are fine. If you write your own, use low + (high - low) / 2.