Using Binary Search in Java

Binary search is a search algorithm that searches for an element, or key, by repeatedly dividing the array in half while it searches for the key. It is faster than linear search, which searches each element of an array sequentially.

Java makes it easy to use binary search in your programs. The java.util.Arrays class provides several versions of the binarySearch() function that find different types of keys, using various options.

It is important to note that the binary search algorithm requires that you sort the array before using binary search. The Java Arrays class conveniently provides a sort() method that sorts an array in increasing order.

Here is a binary search example. First, import the Arrays class:

import java.util.Arrays;

Next, create a sample array named arr:

int[] arr = {10, 1, 3, 20, 99, 5, 8, 2, 4};

To sort the array in increasing order, call the sort() method on arr:

Arrays.sort(arr);

Let's output the array to verify that it is sorted:

System.out.println( Arrays.toString(arr) ); // [1, 2, 3, 4, 5, 8, 10, 20, 99]

Now that the array is sorted, we can use the binarySearch() function. This statement searches for the value 20 in the array:

System.out.println( Arrays.binarySearch(arr, 20) ); // 7

The binarySearch() function returns the index of the key in the array if it finds it. In this case, the return value is 7, since 20 is at position 7 of the array.

If the key is not found in the array, the binarySearch() function returns a negative number that follows this formula:

(-(insertion point) - 1)

The insertion point is the index of the first element that is greater than the key or the length of the array if all elements are less than the key.

Here is a binary search that fails:

System.out.println( Arrays.binarySearch(arr, 7) ); // -6

In this example, the insertion point is 5; the value 8 is the first element that is greater than the key 7, and its index is 5. With 5 as the insertion point value, the formula gives the return value -(5) - 1 or -6.

Here is the complete program:

import java.util.Arrays;

public class Example {
  public static void main(String[] args) {

    int[] arr = {10, 1, 3, 20, 99, 5, 8, 2, 4};

    Arrays.sort(arr);

    System.out.println( Arrays.toString(arr) );

    System.out.println( Arrays.binarySearch(arr, 20) ); // 7

    System.out.println( Arrays.binarySearch(arr, 7) ); // -6

  }
}

Remember to keep the array sorted if the array elements ever change. Just call the Arrays.sort() method on the array to sort it again.

Thanks for reading.

Follow me on Twitter @realEdwinTorres for more programming tips. 😀