Recursive Binary Search Implementation in Java

사용하여 응답함: GPT-4o-mini에 의해Java Q&A Hub

질문:

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);
        }
    }
}

Explanation:

  1. 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.

    • If the left index exceeds the right index, it returns -1, indicating that the target is not found.
    • It calculates the middle index and checks if the target is equal to the middle element.
    • If the target is less than the middle element, it recursively searches the left half of the array.
    • If the target is greater than the middle element, it recursively searches the right half of the array.
  2. search Method: This is a helper method that initializes the left and right indices and calls the binarySearch method.

  3. 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.

Usage:

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.