Coffee break #156. How to use Arrays.binarySearch() method in Java

Source: FreeCodeCamp With this article, you will learn how to use the Arrays.binarySearch() method in Java.

What is Arrays.binarySearch() in Java?

The official documentation for the Arrays.binarySearch() method states:

• This method searches the specified byte array for the specified value using a binary search algorithm.
• The array must be sorted (using the sort(byte[]) method ) before the call is made. If it is not sorted, the results will not be determined.
• If the array contains multiple elements with the specified value, there is no guarantee which one will be found.

In simple terms, the Arrays.binarySearch() method can search for a given element in a sorted array and return its index if found.

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';

		int foundItemIndex = Arrays.binarySearch(vowels, key);

		System.out.println("The given vowel is at index: " + foundItemIndex);

	}
}

The Arrays.binarySearch() method takes the array you want to search as the first argument and the key you are searching for as the second argument. The output of the above program will be: Remember that the method returns the index of the element found, not the element itself. This way you can store the index as an integer like the one used in this example. By default, the method uses the first index of the array as the starting point of the search and the length of the array as the ending point of the search. In this case, the starting index is 0 and the ending index is 6. Instead of using the default starting and ending index, you can define them yourself. For example, if you want to search from index 2 to index 4, you could do it like this:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';
		int startIndex = 2;
		int endIndex = 4;

		int foundItemIndex = Arrays.binarySearch(vowels, startIndex, endIndex, key);

		System.out.println("The given vowel is at index: " + foundItemIndex);

	}
}

In this case, the Arrays.binarySearch() method takes the array you want to search as the first argument, the starting index as the second argument, the ending index as the third, and the key as the fourth. As long as you keep the ending index within the length of the array, the method should work fine. But if you exceed it, you will get an Array index out of range exception . It's pretty simple, right? The method returns the index of the element if it is found. But what happens if it doesn't find the given element?

What happens when Arrays.binarySearch() doesn't find a given element?

Let's take another look at the official documentation for the Arrays.binarySearch() method :

• The method finds the index of a key in the search results if it is contained in the array within the specified range; otherwise we get (-(insertion point) - 1) .
• The insertion point is defined as the point at which a key will be inserted into the array: the index of the first element in the range is greater than the key, or toIndex (end index) if all elements in the range are less than the specified key.
• Note that the return value will only be greater than or equal to 0 when the key is found.

Not very clear, right? The first line states that the method will return the index of the key from the search if it is found in the array. If it is not found, then the output will be equal to the value (-(insertion point) - 1) . Depending on the search key, insertion point can have different meanings. Let's say we have an array [5, 6, 7, 8, 9, 10] and a search key of 0 , which is clearly not in the array. In this case, the search key is less than all the elements of the array. But the first element that is greater than the search key is 5 . Thus, in our case the insertion point will be: You can implement this in a code snippet like this:

package arrays;

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		System.out.println(Arrays.binarySearch(numbers, 0)); // -1
	}
}

Let's assume again that we have an array [5, 6, 7, 8, 9, 10] and a search key of 12 , which is clearly not in the array. In this case, the search key is greater than all the elements of the array. Here the insertion point will be like this: Remember that if you don't manually specify the ending index, the method uses the length of the array as the ending index, which in this case is 6 . You can implement this in a code snippet like this:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		System.out.println(Arrays.binarySearch(numbers, 12)); // -7
	}
}

However, the results will change if you define the start and end indexes manually:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		int startIndex = 1;
		int endIndex = 3;

		System.out.println(Arrays.binarySearch(numbers, startIndex, endIndex, 5)); // -2
		System.out.println(Arrays.binarySearch(numbers, startIndex, endIndex, 10)); // -4

	}
}

Try to calculate the values ​​yourself. You can also use the Arrays.binarySearch() method with symbols like this:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';
		int startIndex = 2;
		int endIndex = 4;

		System.out.println(Arrays.binarySearch(vowels, startIndex, endIndex, key));

	}
}

The same principles apply if the specified search key is not found. But when comparing between a character in the array and a given search key, the ASCII code of the corresponding character will be used. That is, A (65) will be less than a (97) . Take this into account when cross-checking your program's output.