Arrays BinarySearch Java | Arrays.binarySearch() in Java

In this tutorial, we are going to learn and understand the binarySearch method from the Arrays class in Java. The thing is that the Arrays class has some very useful methods related to arrays, for doing different things, and the binarySearch method is one such method.

This is related to the binary search algorithm, and if you are familiar with the algorithm, you would easily get that. But if you are not familiar with the binary search algorithm, we would discuss that too in brief here. So, let’s begin the discussion about the Arrays.binarySearch() method in Java

What is the Arrays.binarySearch() method in Java?

To understand this method, we just need to understand what is the task here. Here, we would have an array, and a key, and we need to search for the key in the array. If the key is found, we need to return the index of that element in the array. The task is very simple, and to perform the binary search, we have the binarySearch method in the Arrays class.

Let’s have a look at an example, through which, we can get multiple things, like how to use the binarySearch method, syntax, and the conditions for using the method. Here are some points which should be followed while using the binarySearch method.

• With method overloading, we have different versions of the binarySearch method, for covering different datatypes.
• On a very basic note, we need to pass an array and the key to the binarySearch method.
• The array that we are passing to the binarySearch method should be sorted. This is necessary. If the array is not sorted, then the results are undefined.
• Using the binarySearch method, the specified key would be searched in the array.
• If the array contains multiple elements with the specified value, then there is no guarantee of which one would be found.
• If the key is found, the method would return the index of the element(not the element itself). Also, if the element is not found, it returns (-(insertion point) – 1). Here, the insertion point is the point, at which, the key would be inserted. This simply means that the return value would be positive, if and only if the key is found in the array.

So, keeping these things in mind, let’s have a look at an example now, through which, we would understand the binarySearch method from the Arrays class, and also we would understand the above points in practice.

Note that in the below example, we are considering an int array and an int key. You can consider some other arrays and similar keys.

import java.util.Arrays;
public class Main{
    public static void main(String[] args){
    int[] arr = new int[] {4, 14, 31, 57, 65, 89};
    int key = 31;
    int index = Arrays.binarySearch(arr, key);
    System.out.println(index);
    }
}

As you can see in the above program, we have an array and the key, and we are calling the binarySearch method, passing the array and key. The binarySearch method returns the index of the key if the key is found in the array. Otherwise, it returns (-(insertion point) – 1). Here, the insertion point is the point at which, the key would be inserted.

If you try to execute the above program, you can find that the output is 2, which is the index at which 31 is present. You can try changing the key, and the array as well, and observe the other outputs.

In the above program, if the key that we are searching for is 32, then the output is going to be -4, which means 3 would be the insertion point, and according to the formula, the output is going to be -4.

So, this is how the binarySearch method works. You can also try using the binarySearch method, changing the arguments that we are passing. This means that you can also try for some other array and key, and other arguments.

Have a look at this another example, using which, we can understand the binarySearch method, for other input. In the below example, first, we would sort the array, using the sort method from the Arrays class, and then we would perform the binarySearch. So, let’s have a look at an example –

import java.util.Arrays;
public class ArrayBasic {
public static void main(String[] args) {
    int[] x = new int[] {56, 45, 34, 67, 89, 29, 31};
    Arrays.sort(x); // because the array needs to be sorted
    System.out.println(Arrays.binarySearch(x, 67));
    }
}

So, in the above example, you can see that the array that we have is not sorted, but we are sorting it, using the sort method. After that, we are performing the binary search, using the binarySearch method. So, the output in the above case is going to be 3, which is the index of the required element. You can try executing the above program and observing the output.

On the other hand, in the above program, if the key that we are searching for is 59, then the output would be negative since the key is not there in the array. Let’s have a look at the program, through which we can understand this.

import java.util.Arrays;
public class ArrayBasic {
public static void main(String[] args) {
    int[] x = new int[] {56, 45, 34, 67, 89, 29, 31};
    Arrays.sort(x); // because the array needs to be sorted
    System.out.println(Arrays.toString(x));
    System.out.println(Arrays.binarySearch(x, 59));
    }
}

As you can see in the above program, the key that we are searching for here is 59 in the array, and it is not present in the array. So, this time, the insertion point of the element in the array would be 5, so the output here would be -6. So, in this way, the method for binary search works in Java.

We can also pass some other arguments, like fromIndex, and toIndex, which are basically integers, and they are given to define the range to search in the specified array. Let’s have a look at an example, through which, we can understand this as well. We will try to give these additional arguments.

Note that here, the fromIndex specifies the index of the first element to be searched. On the other hand, the toIndex specifies the index of the last element to be searched. The toIndex is exclusive.

import java.util.Arrays;
public class Main{
public static void main(String[] args){
    int[] arr = new int[] {4, 14, 31, 57, 65, 89, 191, 267, 451, 677};
    int key = 89;
    int index = Arrays.binarySearch(arr, 1, 6, key);
    System.out.println(index);
    }
}

As you can see in the above program, we have provided 4 arguments to the binarySearch method. The first is the array, the second is the fromIndex, the third is the toIndex, and the last is the key itself. So here, we are searching from the fromIndex, up to the toIndex(exclusive), for the key in the array.

In this case, we are searching for 89 in the array, from Index 1 to index 6(exclusive). The output in this case is going to be 5, which is the index of the key in the sorted array.

On the other hand, if here, the element is not found, again the output is going to be negative, according to the formula. So, from this, we can understand that we can specify more arguments, like fromIndex and toIndex, to specify a search range.

How is binary search implemented (in brief)?

Well, till now you might have understood the binarySearch method from the Arrays class in Java. But in general, how is the binary search algorithm implemented? Let’s explain this in simple terms. Also, we would get to know here, that why the array should be sorted in the case of binary search.

Before moving towards the theoretical part of this question, let’s have a look at a quite practical example, through which, you can understand many things related to binary search.

Let’s consider that you have a big book, which has several hundreds of pages, and you need to open page number 534. Now, one approach that is possible here, is that you would simply go one page forward at a time, and stop once you reach the required page. But, can we do anything better than this? Certainly yes!

So, another approach here can be that you would open the book at some random page number, and check if that page number is equal to the required page number. If that page number is the same as what you need, you would stop the search. Otherwise, there are two more possibilities, that the page number would be smaller than the required, or larger than the required.

Now, if the page number is smaller than the required page number, then you know that you need to turn the pages after that, and otherwise, you need to turn the pages before that.

So, turning the pages before and after according to the situation, you would reach the required page. Something similar to this is going to happen in the case of binary search here.

Here, the array needs to be sorted, which makes sense, because the pages in the book are also in the sorted order, and we could reach the required page number quickly.

So, let’s say that our array is sorted, and for example, let’s consider this array –

{4, 14, 31, 57, 65, 89}

Also, in this array, we want to search for 65. So, the key is 65. To search for the key here, we need to do several things, which are mentioned here –

• First of all, you consider the starting and ending point as the first and last index of the array.
• Having them, you need to get the mid index, which can be calculated as (start+end)/2.
• After that, we need to compare the element on the mid-index, with the key.
• If the element on the mid index is equal to the key, then we simply need to return the key.
• Otherwise, there are two possibilities, the element at the mid-index may be smaller than the key, or greater than the key.
• If the mid element is smaller than the key, then we would need to change the start index, to mid + 1, and repeat the same process for the new start and end.
• Otherwise, if the mid element is greater than the key, then we need to change the end index, to mid – 1, and repeat the same process for the new start and end.
• Once, the start becomes greater than the end, we can say that the element is not there in the array.

So, in this way, we can generally consider how the binary search algorithm is carried out. When the array is sorted, we are sure about what side we need to search, just as we are sure when we need to turn the pages to find the required page in the book.

So, we hope that you got the implementation of the binary search, from the above example, and also the binarySearch method from the Arrays class. You can use the method in the program as and when required, but be sure about the conditions of performing the binary search.

FAQ About Arrays BinarySearch Java