BinarySearch() in Java

In Java, binarySearch() is a method that helps in searching a particular key element from several elements using the binary search algorithm. In order to perform this operation, elements have to be sorted in ascending order. If it is not sorted, it can be sorted using the method Arrays.sort(arr). Otherwise, results are said to be undefined.  Compared to linear search, binary search is considered to be faster. Due to this, the binary search’s time complexity is said to be O(log n). Moreover, the binarySearch() method can be instantiated from the package java.util.Arrays. More details on the binarySearch() method will be discussed in the following sections.

Syntax:

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

public static int binarySearch(Object[] a, Object key)

Here, the parameters a and key are the array that has to be searched and the value to be found, respectively.

binarySearch() method returns the index of the key element that was searching for. In the case where the key element is not found, an insertion point where the key element that would have been inserted will be returned. If the search’s key element is not comparable to other elements in the array, an exception known as ClassCastException will be thrown.

How BinarySearch() Method Works in Java?

Let us see how this method works in Java:

1. Suppose k is the key element that has to be searched for. Compare k with the array’s middle element.
2. If k is matched with the element in the middle position, the mid-index has to be returned.
3. Else, If k is higher than the element in the middle position, then k can be found only on the right side of the mid element.
4. Otherwise, it can be found on the left side of the middle element.

Examples to Implement BinarySearch() in Java

Below are examples of some programs on the BinarySearch() method.

Example #1

Code:

import java.util.Arrays;
public class BinarySearchExample
{
public static void main(String[] args)
{
//create a byte array
byte ba[] = {05, 10, 15, 20, 25, 30};
//create a character array
char ca[] = {'a', 'n', 's', 'p', 'v', 'i', 'd'};
//create an integer array
int ia[] = { 10, 20, 15, 22, 35};
//create a double array
double da[] = {10.1 , 15.34 , 22.25, 13.5};
//create a float array
float fa[] = {13.2f, 25.1f , 22.2f , 43.5f };
//sort all the arrays that created above
Arrays.sort(ba);
Arrays.sort(ca);
Arrays.sort(ia);
Arrays.sort(da);
Arrays.sort(fa);
//enter the key elements that has to be searched in the array
byte bKey = 15;
char cKey = 'i';
int iKey = 22;
double dKey = 15.34;
float fKey = 22.2f;
System.out.println("Element "+ bKey + " is found at the position of " + Arrays.binarySearch(ba,bKey) );
System.out.println("Element "+ cKey + " is found at the position of " + Arrays.binarySearch(ca,cKey) );
System.out.println("Element "+ iKey + " is found at the position of " + Arrays.binarySearch(ia,iKey) );
System.out.println("Element "+ dKey + " is found at the position of " + Arrays.binarySearch(da,dKey) );
System.out.println("Element "+ fKey + " is found at the position of " + Arrays.binarySearch(fa,fKey) );
}
}

Output:

Certain arrays of different types such as character, integer, float, double, and bytes are created after sorting the arrays using Arrays in the above program.Sort() method, elements that have to be searched in the arrays are declared. Then the index of the searched element is printed using the Arrays.binarySearch() method.

Suppose a key element is given that is not present in the array; what will be the output??

In order to find that, let us change the code of key elements as shown below.

byte bKey = 15;
char cKey = ‘i’;
int iKey = 89;
double dKey = 15.34;
float fKey = 22.2f;

That is, iKey=89 is not present in the array, then the output will be displayed as below.

As we can see, the position is printed as -6. It is because if an element is searched and not found, the index’s negative value will be returned if that element was present. i.e ,int ia[] = { 10, 20, 15, 22, 35} is the given array. If 89 were present, the array would have been int ia[] = { 10, 20, 15, 22, 35, 89};

It can be clearly seen that the index would have been 6. As it is not present in the original array, that particular index’s negative value is returned in the above output.

Example #2

A binary search can also be done with the help of recursion, as shown below.

Code:

//sample class
class BinarySearchExample{
public static int binarySearch(int a[], int f, int l, int k){
//if last element is greater than or equal to first element
if (l>=f)
{
//find the mid
int m = f + (l - f)/2;
//if the key element that is searching is found in middle position, return mid position
if (a[m] == k)
{
return m;
}
//if key element is less than element in middle position, search the left <u>subarray</u>
if (a[m] > k){
return binarySearch(a, f, m-1, k);
}
//if key element is greater than the element in middle position, search the right <u>subarray</u>
else{
return binarySearch(a, m+1, l, k);
}
}
return -1;
}
public static void main(String args[]){
//initialise the array
int a[] = {34,45,54,68,79};
int k = 68;
int l = a.length-1;
//store the position in variable res
int res = binarySearch(a,0,l,k);
if (res == -1)
System.out.println("Sorry!! Can't find the element....!");
else
System.out.println("Element is found at the position: "+res);
}
}

Output:

In the above program, an array is created first, and the element to be found out is also declared. Using the binarySearch() method, the position of the key elements will be found out.  Suppose the element is not found, a message will be printed as “Sorry !!!Can’t find the element”.

Conclusion

binarySearch() is a Java method that helps find a particular key element among several elements available in the array using the binary search algorithm. Working and examples of this method are explained in this document in detail.

Recommended Article

This is a guide to BinarySearch() in Java. Here we discuss how the BinarySearch() Method Works in Java and examples with code implementation. You can also go through our other suggested articles to learn more –

1. JavaScript Math Functions
2. Layout in Java
3. Java Compilers
4. Merge Sort In Java

The above is the detailed content of BinarySearch() in Java. For more information, please follow other related articles on the PHP Chinese website!