`Arrays.binarySearch`

A binary search algorithm uses guessing to quickly locate a value in a sorted array. It repeatedly chooses two elements. The next guess is based on their values.

In large arrays, binary search is much faster than a linear search. It is typically slower than a lookup table or hash table. But it may use less memory.

`BinarySearch` example

It is simple, but this example demonstrates binarySearch. Please notice the input array (values): it is presorted. We search for 8 in the array.

And Value 8 is located at index 7. BinarySearch correctly located this value in the array.

import java.util.Arrays;

public class Program {
    public static void main(String[] args) {

        // A presorted array.
        int[] values = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        // Find value 8.
        int index = Arrays.binarySearch(values, 8);

        // Display result.
        System.out.println("Index = " + index);
        System.out.println("Value = " + values[index]);
    }
}Index = 7
Value = 8

Not found

BinarySearch returns a negative number if the value cannot be found. In this example we search for the value 400, but it does not exist. A negative number is instead returned.

import java.util.Arrays;

public class Program {
    public static void main(String[] args) {

        int[] values = { 0, 2, 4, 8 };

        // Value does not occur.
        int index = Arrays.binarySearch(values, 400);
        System.out.println(index);
    }
}
-5

Benchmark, search

BinarySearch is faster on larger arrays, but slower on short ones. On a 100-element int array, it is faster than a linear search for finding an element at index 80.

Version 1 In this version of the code we use Arrays.binarySearch to find an element in a 100-element int array.

Version 2 Here we use a simple for-loop that iterates in order from low to high indexes to search the array.

Result For short, 10 element int array, a simple for-loop with a linear search is faster. BinarySearch can make programs slower.

import java.util.Arrays;

public class Program {
    public static void main(String[] args) throws Exception {

        // Create 100 element array.
        int[] values = new int[100];
        for (int i = 0; i < 100; i++) {
            values[i] = i;
        }

        long t1 = System.currentTimeMillis();

        // Version 1: search with binarySearch.
        for (int i = 0; i < 1000000; i++) {
            int index = Arrays.binarySearch(values, 80);
            if (index != 80) {
                throw new Exception();
            }
        }

        long t2 = System.currentTimeMillis();

        // Version 2: search with for-loop (linear).
        for (int i = 0; i < 1000000; i++) {
            int index = -1;
            for (int j = 0; j < values.length; j++) {
                if (values[j] == 80) {
                    index = j;
                    break;
                }
            }
            if (index != 80) {
                throw new Exception();
            }
        }

        long t3 = System.currentTimeMillis();

        // ... Times.
        System.out.println(t2 - t1);
        System.out.println(t3 - t2);
    }
} 23 ms, Arrays.binarySearch
113 ms, for-loop (linear search)

Consider lookups

When developing a program, I usually choose a lookup table (HashMap) for searching. This is fastest, but may use more memory. It does not accommodate all searches.

A rare case

Few programs use sorted arrays that cannot be stored in a lookup table. But when required, binarySearch can be useful, or even make a program possible.