Arrays.binarySearchExamine the Arrays.binarySearch method. Test the 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.
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); } }
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.
No updates found for this page.
© 2007-2023 Sam Allen.