Arrays.binarySearch

https://www.dotnetperls.com/binarysearch-java

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.

Based on: Java 8

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.