Implement Binary Search in Java using recursion.
Certainly! Below is an implementation of the Binary Search algorithm in Java using recursion. This implementation assumes that the input array is sorted in ascending order.
public class BinarySearch {
// Recursive method to perform binary search
public static int binarySearch(int[] arr, int left, int right, int target) {
// Base case: if the left index exceeds the right index, the target is not found
if (left > right) {
return -1; // Target not found
}
// Calculate the middle index
int mid = left + (right - left) / 2;
// Check if the target is present at mid
if (arr[mid] == target) {
return mid; // Target found
}
// If the target is smaller than mid, search in the left half
if (target < arr[mid]) {
return binarySearch(arr, left, mid - 1, target);
}
// If the target is larger than mid, search in the right half
return binarySearch(arr, mid + 1, right, target);
}
// Helper method to initiate the binary search
public static int search(int[] arr, int target) {
return binarySearch(arr, 0, arr.length - 1, target);
}
public static void main(String[] args) {
int[] arr = {2, 3, 4, 10, 40};
int target = 10;
int result = search(arr, target);
if (result == -1) {
System.out.println("Element not found in the array.");
} else {
System.out.println("Element found at index: " + result);
}
}
}
binarySearch Method: This is the recursive method that performs the binary search. It takes the array, the left and right indices, and the target value as parameters.
search Method: This is a helper method that initializes the left and right indices and calls the binarySearch
method.
main Method: This is the entry point of the program where an example array and target value are defined. It calls the search
method and prints the result.
You can run this code in any Java environment. Just make sure to modify the arr
and target
variables in the main
method to test with different inputs.