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.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.