HomeSearch

Java Arrays.binarySearch Use

This Java article examines the Arrays.binarySearch method. It tests performance of binary and linear searching.
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.

Java program that uses Arrays.binarySearch 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]); } } Output 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.
Java program that cannot locate element 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); } } Output -5
Searching benchmark. 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.

But: For short, 10 element int array, a simple for-loop with a linear search is faster.

Also: The for-loop will be faster if the element is located near the start of the linear search (in an early element).

So: BinarySearch is no guaranteed performance boost. Often it makes programs slower. And the sort requirement can be a burden.

Java program that times Arrays.binarySearch 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(); // ... 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(); // ... 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); } } Output 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.HashMap
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.
© 2007-2019 Sam Allen. Every person is special and unique. Send bug reports to info@dotnetperls.com.
Home
Dot Net Perls