Java Arrays.binarySearch

Examine 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.Array

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

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.

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(); // 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); } } 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.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

Java Arrays.binarySearch

Related Links:

.Net

Java

Related Links