Binary search is used to find an element among many other elements. The binary search method is faster than the linear search method. The array members must be in ascending order for binary search. To get rid of the unsorted arrays, you can use the Arrays.sort(arr) method to sort it.
Java Linear Search
A simple strategy for searching is linear search. The array is scanned progressively in this method, and each element is compared to the key until the key is found or the array is reached.
In real-world applications, linear search is rarely used. Because binary search is substantially faster than linear search, it is the most commonly utilized strategy. There are three techniques to execute a binary search in Java:
- Using the iterative approach
- Using a recursive approach
- Using Arrays.binarySearch () method.
All three techniques will be implemented and discussed in this session.
Binary search algorithm in Java
The collection is repeatedly divided in half in the binary search technique. The main item is found in the collection’s left or right half based on whether the key is less than or greater than the collection’s mid element.
The following is a basic Binary Search Algorithm:
- Calculate the collection’s middle element.
- Compare and contrast the key elements with the central element.
- We return the central index position for the key discovered if the key Equals the middle element.
- Else If key > mid element, the key is located in the collection’s right half. As a result, repeat steps 1–3 on the collection’s lower (right) half.
- Otherwise, if the key is in the central element, the key is in the upper half of the collection.
- As a result, the binary search in the upper half must be repeated.
As you can see from the preceding stages, half of the elements in the collection are rejected after the first comparison in the Binary search. It’s worth noting that the identical techniques apply to both iterative and recursive binary searches. As a result, we divide the array several times and decide which half to search for the key by comparing the key element to the mid. Binary search is highly efficient as far as time and accuracy and is much faster.
Java Binary Search Implementation
Let’s use the strategy mentioned above to create a Binary search application in Java that uses an iterative approach. We use an example array in this program and do a binary search.
import java.util.*;
class Codeunderscored {
public static void main(String args[]){
int numArray[] = {10,15,20,25,30,35,40};
System.out.println(" array input: " + Arrays.toString(numArray));
//relevant key to be searched
int key = 35;
System.out.println("\nSearched key=" + key);
//set start_idx to the array's first index
int start_idx = 0;
//set end_idx to the last elements in array
int end_idx=numArray.length-1;
//calculate the array's mid_idx
int mid_idx = ( start_idx + end_idx)/2;
//as long as the first and last do not overlap
while( start_idx <= end_idx ){
//if the mid < key, then key to be searched is in the first half of array
if ( numArray[mid_idx] < key ){
start_idx = mid_idx + 1;
}else if ( numArray[mid_idx] == key ){
//if key = element at central, then go ahead and print the location
System.out.println("Item found at index: " + mid_idx);
break;
}else{
// search for the key in the array's second half
end_idx = mid_idx - 1;
}
mid = ( start_idx + end_idx)/2;
}
//if start_idx and end_idx overlap, then key is not present in the array
if ( start_idx > end_idx ){
System.out.println("Item not found!");
}
}
}
The given program demonstrates an iterative Binary search method. An array is declared first, followed by a key to be searched. After determining the array’s central element, the key is compared to the central element. The key is then searched in the lower or upper half of the array based on whether it is less than or greater than the key.
Performing Recursive binary search in Java
You can also use the recursion approach to execute a binary search. The binary search strategy is used here recursively until the key is located or the list is exhausted.
The following is the program that implements a recursive binary search:
import java.util.*;
class Codeunderscored{
// binary search via recursive approach
public static int binary_Search(int intArray[], int start_idx, int end_idx, int key){
// If the array is in order, execute a binary search on it.
if (end_idx>=start_idx){
//calculate mid
int mid_idx = start_idx + (end_idx - start_idx)/2;
//if key =intArray[mid_idx] return mid_idx
if (intArray[mid_idx] == key){
return mid_idx;
}
//if intArray[mid_idx] > key then key is in left half of array
if (intArray[mid_idx] > key){
return binary_Search(intArray, start_idx, mid-1, key);// searching for the key recursively
}else //key is present in the array's right half
{
return binary_Search(intArray, mid_idx+1, end_idx, key);//recursively search for key
}
}
return -1;
}
public static void main(String args[]){
// array and key definition
int intArray[] = {11,21,31,41,51,61,71,81,91,101};
System.out.println("Input List: " + Arrays.toString(intArray));
int key = 31;
System.out.println("\nThe key we are looking for is:" + key);
int end_idx=intArray.length-1;
//calling the binary search method
int result = binary_Search(intArray,0,end_idx,key);
//printing the result
if (result == -1)
System.out.println("\nKey is not available in the provided list!");
else
System.out.println("\nKey is available at position: "+result + " in the list");
}
}
Using Arrays.binarySearch () function
The Arrays class in Java includes a ‘binarySearch ()’ method that executes the binary search on the provided array. The given array and the key to be searched are sent as parameters, and the position of the key in the array is returned. The method returns -1 if the key cannot be found.
The Arrays.binarySearch () method is implemented in the example below.
import java.util.Arrays;
class Codeunderscored{
public static void main(String args[]){
// array definition
int intArray[] = {20,30,40,50,60,70,80,90,100};
System.out.println(" Array input is : " + Arrays.toString(intArray));
//establish the key we want to search for
int key = 60;
System.out.println("\nThe key we are looking for is:" + key);
//calling the binarySearch method on the provided array given the key to be searched
int result = Arrays.binarySearch(intArray,key);
//printing the return result
if (result < 0)
System.out.println("\nKey is not available in the provided array!");
else
System.out.println("\nKey is available at index: "+result + " in the array.");
}
}
Java Iterative Binary Search Example
Let’s look at a binary search example in Java.
class BinarySearchExample {
public static void binarySearch(int arr[], int first, int last, int key){
int mid_idx = (start_idx + end_idx)/2;
while( start_idx <= end_idx ){
if ( arr[mid_idx] < key ){
start_idx = mid_idx + 1;
}else if ( arr[mid_idx] == key ){
System.out.println("Element is available at the index: " + mid_idx);
break;
}else{
end_idx = mid_idx - 1;
}
mid_idx = (first_idx + last_idx)/2;
}
if ( first_idx > last_idx ){
System.out.println("Element is not available!");
}
}
public static void main(String args[]){
int arr[] = {20,30,40,50, 60};
int key = 40;
int end_idx=arr.length-1;
binarySearch(arr,0,end_idx,key);
}
}
Example of a Binary Search in Java with Recursion
Let’s look at an example of binary search in Java, where we’ll use recursion to find an element from an array.
class BinarySearch{
public static int binarySearch(int arr[], int first, int last, int key){
if (last>=first){
int mid_idx = start_idx + (end_idx - start_idx)/2;
if (arr[mid_idx] == key){
return mid_idx;
}
if (arr[mid_idx] > key){
return binarySearch(arr, start_idx, mid_idx-1, key);//searching for the key in left subarray
}else{
return binarySearch(arr, mid_idx+1, end_idx, key);//searching for the key in right subarray
}
}
return -1;
}
public static void main(String args[]){
int arr[] = {20,30,40,50,60};
int key = 40;
int end_idx=arr.length-1;
int result = binarySearch(arr,0,end_idx,key);
if (result == -1)
System.out.println("Element is not available!");
else
System.out.println("Element is available at the index: "+result);
}
}
Example: Binary Search in Java using Arrays.binarySearch()
import java.util.Arrays;
class BinarySearch{
public static void main(String args[]){
int arr[] = {20,30,40,50, 60};
int key = 40;
int result = Arrays.binarySearch(arr,key);
if (result < 0)
System.out.println("Element is not available in the array!");
else
System.out.println("Element is available at the index: "+result);
}
}
Conclusion
This tutorial has covered Binary Search and Recursive Binary Search in Java and their algorithms, implementations, and Java Binary Search code examples. In Java, binary search is the most commonly used search method. First, the data provided must be sorted in ascending order before a binary search.
In Java, a binary search is a mechanism for looking for a certain value or key in a collection. It’s a key-finding method that employs the “divide and conquers” strategy. The collection on which a Binary search will be used to find a key should be sorted in ascending order. Typically, most programming languages support Linear search, Binary search, and Hashing strategies for searching for data in a collection.
