Introduction to 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 time complexity of the binary search 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:
public static int binarySearch(Object[] a, Object key)
Here, the parameters a and key are the array that has to be searched and 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 key element that is searched 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:
- Suppose k is the key element that has to be searched for. Compare k with the array’s middle element.
- If k is matched with the element in the middle position, mid-index has to be returned.
- 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.
- Otherwise, it can be found on the left side of the middle element.
Examples to Implement BinarySearch() in Java
Below are the 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:
In the above program, certain arrays of different types such as character, integer, float, double, bytes are created. After sorting the arrays using Arrays.Sort() method, elements that has to be searched in the arrays are declared. Then the index of the searched element is printed using Arrays.binarySearch() method.
4.8 (7,000 ratings)
View Course
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 due to the fact that, if an element is searched and not found, the negative value of the index 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, the negative value of that particular index is returned in the above output.
Example #2
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 subarray
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 subarray
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 method in Java that helps in finding a particular key element among several elements available in the array using the binary search algorithm. Working and examples of this method is 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 –
